How to tell Prolog that two literals are equivalent

Question

Anyone knows how to tell Prolog that n(n(p)) and n(p) represent the same thing?

Or how to reduce n(n(p)) to n(p)?

Answer 1

Anyone knows how to tell Prolog that n(n(p)) and n(p) represent the same thing?

Prolog's unification system has a clear meaning of when two things are the same. n(n(p)) and n(p) are not the same thing. You can construct a predicate that defines a more generic equivalence relation than (=)/2.

Normally in Prolog two constants are different if they have a different name. Two compound terms are the same only if the functor is the same (the name of the functor and the number of parameters), and the parameters are equal as well.

We thus can define a predicate like:

equiv_(n(n(p)), n(p)).

equivalence(L, R) :-
    equiv_(L, R).
equivalence(L, R) :-
    equiv_(R, L).
equivalence(L, L).

If you the match with equivalence(n(n(p)), n(p)), it will return true.

@false Can't I define a predicate n(n(p)) that returns n(p). What I want, in fact, is that all occurrences of the within a list to be replaced with the latter.

You can make a predicate that unifies a second parameter with n(p) if the first one is n(n(p)):

replace_nnp(X, n(p)) :-
    X == n(n(p)).
replace_nnp(X, X) :-
    X \== n(n(p)).

Then we can use maplist/3 [swi-doc] to map a list of items to another list of items:

replace_nnp_list(LA, LB) :-
    maplist(replace_nnp, LA, LB).

For example:

?- replace_nnp_list([n(n(p)), p, n(p), n(n(p))], X).
X = [n(p), p, n(p), n(p)] ;
false.