Prolog; if and (stopping) recursion

Question

In trying to better understand prolog, lists and recursion as a whole I'm working my way through various simple tasks I've assigned to myself. Among others is removing double entries from a list.

I've defined a rule:

is_on(Item, [Ah|At]) :- Ah = Item; is_on(Item, At).

This checks if 'Item' is on the list X or not. So I thought I could expand this to define a filter_double predicate as well:

filter_doubles([Ah|At], Result) :-
    (not(is_on(Ah, At)) ->
        Result = [Ah|Result]
    ;
        filter_doubles(At, Result)
    ).

This made perfect sense to me: if Ah doesn't occur in the rest of the list (its tail), then add a to the front of result using list construction, otherwise recurse over the rest of the list. Apparently Prolog thinks otherwise:

47 ?- filter_doubles([1,2,3,3,4,2,1,1], Z).
Z = [3|**]. 

Am I thinking too imperative on this?

Answer 1

You need recursion in both branches, and you need a base case:

filter_doubles([], []).
filter_doubles([X|L], Result) :-
    (memberchk(X,L) ->
        filter_doubles(L, Result)
    ;
        filter_doubles(L, Result0),
        Result = [X|Result0]
    ).

Result = [Ah|Result] indeed seems to be a case of imperative thinking. What in means in Prolog is "unify Result with a term that has Result as its second argument," which either fails (in unification with occurs check) or produces a "rational tree" (an graph structure with a loop, in most Prologs).

Exercise: make the code I posted tail-recursive.

Note that this removes all but the last occurrence of each item.

Answer 2

In logic programming, recursion in a predicate is often handled with more than one rule. The first rule describes the recursion base case, i.e. its halting condition; the other rules, or perhaps just the second one, describe the recursive step(s).

So, your is_on rule (which I have renamed contains) gets typically written in the following fashion:

contains(Item, [Item | _]).
contains(Item, [_ | Tail]) :- contains(Item, Tail).

The filter_double predicate may undergo a similar rewriting. First of all, an empty list will correspond to an empty result.

filter_doubles([], []).

Then, if the Item occurs in the Rest of the list, you recur over the Rest of the list, dropping that occurrence of Item.

filter_doubles([Item | Rest], Result) :-
    contains(Item, Rest), !,
    filter_doubles(Rest, Result).

Finally, if the Item does not occur in the Rest of the list (because the preceding rule has already checked out for that case), you are free to place that Item on the front of the result using list construction, and proceed to filter the Rest of the list.

filter_doubles([Item | Rest], [Item | Tail]) :- filter_doubles(Rest, Tail).

Please note that when you attempt to perform accumulation with an expression such as Result = [Ah|Result], Prolog creates an infinitely recursive data structure: Result is unified with a list having Ah as head and Result as tail, which is unified with a list having Ah as head and Result as tail, which is unified with a list having Ah as head and Result as tail, and so on, and so on, and so on.