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.