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?

I suppose you mean is_on(Item, [H|T]) :- Item = H; is_on(Item, T). or is_on(X,L) :- memberchk(X,L). — Fred Foo
Yeah, exactly, hurried making this post, not thinking about that one hehe — Oxymoron
There's also a syntax error (missing paren), and is the predicate called filter_double or filter_doubles? — Fred Foo

Giulio Piancastelli Giulio Piancastelli · Accepted Answer · 2011-03-07T10:05:37

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.

Prolog; if and (stopping) recursion

2 Answers