Check occurrence in Prolog

1
votes

I want to write a predicate occurs(Var, Term) that succeeds if the Prolog variable Var occurs in the Prolog term Term, and fails otherwise.

% occurs(Var, Term)

?- occurs(X, f(X)).
true.

?- occurs(X, f(Y)).
false.

?- occurs(X, f(a,g(b,h(X,c),d))).
true.

I was thinking about such a thing but i want another solution if possible : 

occurs(X,Y):- contains_term(X,Y).
3
prolog
Actually contains_term/2 is not correct because it uses unification. You should use contains_var/2. - Tudor Berariu
By another solution do you mean you are wanting to avoid the existing Prolog predicate contains_var/2 that makes the problem easy? What's your requirement for another solution? If you want to do it "the long way" you would write a recursive rule using (=..)/2. - lurker
See this answer for a similar problem - false

3 Answers

2
votes

A better name which clarifies a bit what you want would be

occurs_in(Var, Term)

Many approaches can use the same techniques as for var_in_vars/2.

This works in any ISO conforming system. It could be quite efficient, too ; that is, being (in the best case) independent of the size of Term.

occurs_in(Var, Term) :-
   \+ subsumes_term(Var, Term).

The next is good as long as you do not have any constraints:

occurs_in(Var, Term) :-
   \+ unify_with_occurs_check(Var, Term).

If you insist on using contains_term/2 — (the name term_subterm/2 would be much more appropriate):

occurs_in(Var, Term) :-
   once( ( contains_term(Term, Subterm), Var == Subterm ) ).

Or, to take into account Prolog superstitions:

occurs_in(Var, Term) :-
   \+ \+ ( contains_term(Term, Subterm), Var == Subterm ).
0
votes

I. Transform Term into a List with =.. Iterate over List

a. check if Head is Term with =..

b. Head == Var?

I uses elemSplit to check if Head has other Atoms stored

elemSplit(X,Out):- nonvar(X), X =.. Y, Y \== [X],
                              append(Y,[],Out), !, true.
elemSplit(_,_):- !, fail.
0
votes

This is how I resolved the problem:

member1(H, [H|_]):-!.

member1(X,[H|T]):-
    atomic(H),!,
    member1(X,T).

member1(X,[H|_]):-
    member1(X,H).

member1(X,[_|T]):-
    member1(X,T).

member1(x, [a,[b,[x,c],d]]).

I would use lists, instead of functions. In this case the predicate returns true if the variable is member in the deep list and false otherwise.

I hope it will help you.