Recursion in prolog, binding to variable

Question

I have a recursive clause that takes a 2 lists, in every recursion call I'm deleting one element from the list and binding this new list (with the element deleted) to a new variable.

This is done properly if I write this variable. But when I have a model it will backtrack making the last binding (the list i need) to that variable undone by the previous binding.

I tried to replicate the situation in this little piece of code:

test([],Test,Result).
test([H|T],Test,Result):-
    member(H,Test),
    delete(Test,H,Test1),
    write(Test1),
    write('\n'),
    test(T,Test1,Test1).
test([H|T],Test,Test1):-
    test(T,Test,Test1). 

?- test([1,2,3],[5,2,4,6,1],R).

I do understand the result should be in the head of the clause like this:

test([H|T],Test,Test1)....

But then only the first recursion call will succeed, something I don't want to.

Any clues of how to tackle this?

Also, i'm fairly new to prolog, just read some tutorials on internet and did simple exercises

Can you please try to clarify what you want your predicate to do ? It's unclear at the moment, to me at least. — m09
Try to describe what are you expecting ?- test([1,2,3],[5,2,4,6,1],R) to returns? — ДМИТРИЙ МАЛИКОВ
The predicate here is just nonsense really, just tried to recreate my other (bigger)clause. What I want is a predicate deletes some elements in a list during a recursion. When I end the recursive that list I get in the end I which as a binding to the variable. I know what I'm doing wrong (every recursion gets an other binding), just no clue how to fix this. — Christophe
So I give a list to the predicate. It will run through it and delete some elements. End list with the deleted elements is what I want. — Christophe

m09 m09 · Accepted Answer · 2012-01-06T18:46:22

filter([], []).

filter([Head|Tail], [Head|Result]) :-
    sometest(Head),
    filter(Tail, Result).

filter([Head|Tail], Result) :-
    \+ sometest(Head),
    filter(Tail, Result).

Now, to see how it works, try to issue a trace/0 call before you run your filter/2 predicate, that'll detail the execution (in swi pl at least) :

Consider this predicate sometest/1 :

sometest(N) :- N mod 2 =:= 0.

now let's trigger the trace mode :

?- trace.
true.

And now, let's call your predicate :

[trace] ?- filter([1, 2, 3], R).
   Call: (6) filter([1, 2, 3], _G522) ? creep
   Call: (7) sometest(1) ? creep
   Call: (8) 1 mod 2=:=0 ? creep
   Fail: (8) 1 mod 2=:=0 ? creep
   Fail: (7) sometest(1) ? creep
   Redo: (6) filter([1, 2, 3], _G522) ? creep
   Call: (7) sometest(1) ? creep
   Call: (8) 1 mod 2=:=0 ? creep
   Fail: (8) 1 mod 2=:=0 ? creep
   Fail: (7) sometest(1) ? creep
   Call: (7) filter([2, 3], _G522) ? creep
   Call: (8) sometest(2) ? creep
   Call: (9) 2 mod 2=:=0 ? creep
   Exit: (9) 2 mod 2=:=0 ? creep
   Exit: (8) sometest(2) ? creep
   Call: (8) filter([3], _G597) ? creep
   Call: (9) sometest(3) ? creep
   Call: (10) 3 mod 2=:=0 ? creep
   Fail: (10) 3 mod 2=:=0 ? creep
   Fail: (9) sometest(3) ? creep
   Redo: (8) filter([3], _G597) ? creep
   Call: (9) sometest(3) ? creep
   Call: (10) 3 mod 2=:=0 ? creep
   Fail: (10) 3 mod 2=:=0 ? creep
   Fail: (9) sometest(3) ? creep
   Call: (9) filter([], _G597) ? creep
   Exit: (9) filter([], []) ? creep
   Exit: (8) filter([3], []) ? creep
   Exit: (7) filter([2, 3], [2]) ? creep
   Exit: (6) filter([1, 2, 3], [2]) ? creep
R = [2] ;
false.

If you take the time to understand what prolog does here, it's basically that : you run as long as you don't find a predicate to be true(the base case, here, filter([], [])), and then you build your list backwards depending on which path you took to reach this case. Here it means that if sometest was true, you add the Head in Result, if not, you don't.

Note that you need to use \+ condition (which means that the condition cannot be proven) in the second clause as I did, or use cut in the first as follows, else, a matching Head will still go through second clause during backtracking :

filter([], []).

filter([Head|Tail], [Head|Result]) :-
    sometest(Head),
    !,
    filter(Tail, Result).

filter([Head|Tail], Result) :-
    filter(Tail, Result).

Now, if you use swi-pl, note that you can directly use include/3 to achieve what you want (it's certainly present in other implementations as well in this name or another) :

?- include(sometest, [1, 2, 3, 4, 5], R).
R = [2, 4].

Hope it helped.

Recursion in prolog, binding to variable

1 Answers