Backtracking issue SWI-Prolog

1
votes

i have some issues with backtracking in SWI-Prolog

In my predicate i have 2 lists as an input and the result is a third one.

I take from L1 each element with nth0/3, then i use another predicate that i need, so i append to the third list the second and the element if other_pred is true. I'm using fail to force backtracking with nth0, but obviously the mypred fails every time and i can't get the final list i want.

I have also tried to use nth0 with and index I, increasing it, but it also makes fail the predicate. Same problem if i check that I is lower than L1 length for each iteration.

mypred(L1, L2, Result) :-

    nth0(_, L1, X),
    other_pred(X, L2),
    append(L2, [X], Result), fail.
1
prologbacktrackingswi-prolog
What are you trying to do here? Bindings are undone when you backtrack, so you cannot use a failure-driven loop to incrementally build a result. - Daniel Lyons
Ok, can i do something in an iterative way or something else? - Aonna
Yes, recursively build up the result. I think you want to have a base case when L1 is empty and then a recursive case when L1 starts with X. What does other_pred/2 do with X and L2? If it can fail, then you need to decide if the whole thing fails or if you just omit that item from the result. In the latter case, you will need a branch or separate clauses to handle the two cases. - Daniel Lyons
You can't use a fail loop like this to keep appending to a list. Try a recursive approach with base case. - lurker
If you don't mind using library(yall), you can do this pretty quickly with maplist: mypred(L1, L2, R) :- maplist([X=Original, X=Y]>>(memberchk(X=New, L2) -> Y=New ; Y=Original), L1, R). - Daniel Lyons

1 Answers

2
votes

Since you did not give code for other_pred/2 this will use member/2.

mypred([H1|T1], L2, [H1|R]) :-
    member(H1,L2),
    mypred(T1,L2,R).

mypred([H1|T1], L2, R) :-
    \+ member(H1,L2),
    mypred(T1,L2,R).

mypred([],_,[]).

Example runs:

?- mypred([1,3,5], [1,2,4,5], R).
R = [1, 5] ;
false.

?- mypred([], [1,2,4,5], R).
R = [].

?- mypred([1,3,5], [], R).
R = [].

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

?- mypred([1,3,5], [1,3,5], R).
R = [1, 3, 5] ;
false.

While you can use nth0/3 using the list constructor |/2 is much better, see: Lists

In this code [H1|T1] and [H1|R] use the list constructor.

This code also uses recursion.

The recursive clauses are

mypred([H1|T1], L2, [H1|R]) :-
    member(H1,L2),
    mypred(T1,L2,R).

mypred([H1|T1], L2, R) :-
    \+ member(H1,L2),
    mypred(T1,L2,R).

because the predicate mypred/3 is called in the clause. Also because the call to mypred/3 is the last call in the clause this is tail-recursive.

The base case for the recursive predicate is

mypred([],_,[]).

How this works for

mypred([1,3,5], [1,2,5], R).

is that the list [1,3,5] for the first parameter is matched with the first predicate 

mypred([H1|T1], L2, [H1|R]) :-
    member(H1,L2),
    mypred(T1,L2,R).

This succeeds with the following unification

H1 = 1
T1 = [3,5]
L2 = [1,2,5]
R = _

The next line in the clause is executed:

member(H1,L2)

This succeeds.

The last line in the clause is executed:

mypred(T1,L2,R)

This matches the first predicate 

mypred([H1|T1], L2, [H1|R]) :-
    member(H1,L2),
    mypred(T1,L2,R).

This succeeds with the following unification

H1 = 3
T1 = [5]
L2 = [1,2,5]
R = _

The next line in the clause is executed:

member(H1,L2)

This fails and backtracks.

Since there is another clause for my_pred/3 it is tried.

mypred([H1|T1], L2, R) :-
    \+ member(H1,L2),
    mypred(T1,L2,R).

This succeeds with the following unification

H1 = 3
T1 = [5]
L2 = [1,2,5]
R = _

The next line in the clause is executed:

\+ member(H1,L2)

This succeeds.

This pattern of trying different clauses for the predicate continues. At this point this will skip the details until the use of the third clause is used.

When the list for the first parameters is [], the third clause is used,

mypred([],_,[]).

Now the backtracking can begin.

Since the only lines that can call the third clause are like

mypred(T1,L2,R).

in the first and second clauses, R is unified with [].

Now depending upon which of the clauses made that call the list in the third parameter will be constructed differently.

If the second clause was used the third parameter will be constructed using 

mypred([H1|T1], L2, R)

So the list is just returned unchanged.

However if the first clause was used the third parameter will be constructed using

mypred([H1|T1], L2, [H1|R])

but this time the result of the third parameter will be the value H1 when the clause was executed combined with the value of R. So if H1 is 5 and R is [] then [H1|R] is [5|[]] which is [5].

Here is a trace run for

mypred([1,3,5], [1,2,5], R).

so that you call look at all of the details.

?- trace.
[trace]  ?- mypred([1,3,5], [1,2,5], R).
   Call: (8) mypred([1, 3, 5], [1, 2, 5], _1844)
   Unify: (8) mypred([1, 3, 5], [1, 2, 5], [1|_2090])
   Call: (9) lists:member(1, [1, 2, 5])
   Unify: (9) lists:member(1, [1, 2, 5])
   Exit: (9) lists:member(1, [1, 2, 5])
   Call: (9) mypred([3, 5], [1, 2, 5], _2090)
   Unify: (9) mypred([3, 5], [1, 2, 5], [3|_2096])
   Call: (10) lists:member(3, [1, 2, 5])
   Unify: (10) lists:member(3, [1, 2, 5])
   Fail: (10) lists:member(3, [1, 2, 5])
   Redo: (9) mypred([3, 5], [1, 2, 5], _2090)
   Unify: (9) mypred([3, 5], [1, 2, 5], _2090)
   Call: (10) lists:member(3, [1, 2, 5])
   Unify: (10) lists:member(3, [1, 2, 5])
   Fail: (10) lists:member(3, [1, 2, 5])
   Redo: (9) mypred([3, 5], [1, 2, 5], _2090)
   Call: (10) mypred([5], [1, 2, 5], _2090)
   Unify: (10) mypred([5], [1, 2, 5], [5|_2096])
   Call: (11) lists:member(5, [1, 2, 5])
   Unify: (11) lists:member(5, [1, 2, 5])
   Exit: (11) lists:member(5, [1, 2, 5])
   Call: (11) mypred([], [1, 2, 5], _2096)
   Unify: (11) mypred([], [1, 2, 5], [])
   Exit: (11) mypred([], [1, 2, 5], [])
   Exit: (10) mypred([5], [1, 2, 5], [5])
   Exit: (9) mypred([3, 5], [1, 2, 5], [5])
   Exit: (8) mypred([1, 3, 5], [1, 2, 5], [1, 5])
R = [1, 5] ;
   Redo: (10) mypred([5], [1, 2, 5], _2090)
   Unify: (10) mypred([5], [1, 2, 5], _2090)
   Call: (11) lists:member(5, [1, 2, 5])
   Unify: (11) lists:member(5, [1, 2, 5])
   Exit: (11) lists:member(5, [1, 2, 5])
   Fail: (10) mypred([5], [1, 2, 5], _2090)
   Fail: (9) mypred([3, 5], [1, 2, 5], _2090)
   Redo: (9) lists:member(1, [1, 2, 5])
   Fail: (9) lists:member(1, [1, 2, 5])
   Redo: (8) mypred([1, 3, 5], [1, 2, 5], _1844)
   Unify: (8) mypred([1, 3, 5], [1, 2, 5], _1844)
   Call: (9) lists:member(1, [1, 2, 5])
   Unify: (9) lists:member(1, [1, 2, 5])
   Exit: (9) lists:member(1, [1, 2, 5])
   Fail: (8) mypred([1, 3, 5], [1, 2, 5], _1844)
false.

If you are using SWI-Prolog then do this combination of queries to bring up the GUI tracer which is nicer for learning.

?- gtrace.
[trace]  ?- mypred([1,3,5], [1,2,5], R).

Per suggestion in comment

Here are some other slight code variations and performance measures. 

mypred_01([H1|T1], L2, [H1|R]) :-
    member(H1,L2),
    mypred_01(T1,L2,R).

mypred_01([H1|T1], L2, R) :-
    \+ member(H1,L2),
    mypred_01(T1,L2,R).

mypred_01([],_,[]).



mypred_02(L1,L2,R) :-
    mypred_02_helper(L1,L2,[],R).

mypred_02_helper([H1|T1],L2,R0,R) :-
    (
        member(H1,L2)
    ->
        mypred_02_helper(T1,L2,[H1|R0],R)
    ;
        mypred_02_helper(T1,L2,R0,R)
    ).

mypred_02_helper([],_,R,R).



mypred_03(L1,L2,R) :-
    mypred_03_helper(L1,L2,[],R0),
    reverse(R0,R).

mypred_03_helper([H1|T1],L2,R0,R) :-
    (
        member(H1,L2)
    ->
        mypred_03_helper(T1,L2,[H1|R0],R)
    ;
        mypred_03_helper(T1,L2,R0,R)
    ).

mypred_03_helper([],_,R,R).



mypred_04(L1,L2,R) :-
    mypred_04_helper(L1,L2,[],R).

mypred_04_helper([H1|T1],L2,R0,R) :-
    (
        memberchk(H1,L2)
    ->
        mypred_04_helper(T1,L2,[H1|R0],R)
    ;
        mypred_04_helper(T1,L2,R0,R)
    ).

mypred_04_helper([],_,R,R).



mypred_05(L1,L2,R) :-
    mypred_05_helper(L1,L2,[],R0),
    reverse(R0,R).

mypred_05_helper([H1|T1],L2,R0,R) :-
    (
        memberchk(H1,L2)
    ->
        mypred_05_helper(T1,L2,[H1|R0],R)
    ;
        mypred_05_helper(T1,L2,R0,R)
    ).

mypred_05_helper([],_,R,R).

Here are the performance results. 

?- findall(N, between(1,100000,N), L1),time(mypred_01(L1,[1,10,100,10000,100000],R)).
% 1,400,020 inferences, 0.109 CPU in 0.103 seconds (106% CPU, 12800183 Lips)
L1 = [1, 2, 3, 4, 5, 6, 7, 8, 9|...],
R = [1, 10, 100, 10000, 100000] ;
% 36 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
false.

?- findall(N, between(1,100000,N), L1),time(mypred_02(L1,[1,10,100,10000,100000],R)).
% 799,988 inferences, 0.063 CPU in 0.062 seconds (101% CPU, 12799808 Lips)
L1 = [1, 2, 3, 4, 5, 6, 7, 8, 9|...],
R = [100000, 10000, 100, 10, 1].

?- findall(N, between(1,100000,N), L1),time(mypred_03(L1,[1,10,100,10000,100000],R)).
% 800,059 inferences, 0.047 CPU in 0.053 seconds (88% CPU, 17067925 Lips)
L1 = [1, 2, 3, 4, 5, 6, 7, 8, 9|...],
R = [1, 10, 100, 10000, 100000].

?- findall(N, between(1,100000,N), L1),time(mypred_04(L1,[1,10,100,10000,100000],R)).
% 299,999 inferences, 0.031 CPU in 0.041 seconds (77% CPU, 9599968 Lips)
L1 = [1, 2, 3, 4, 5, 6, 7, 8, 9|...],
R = [100000, 10000, 100, 10, 1].

?- findall(N, between(1,100000,N), L1),time(mypred_05(L1,[1,10,100,10000,100000],R)).
% 300,005 inferences, 0.031 CPU in 0.032 seconds (98% CPU, 9600160 Lips)
L1 = [1, 2, 3, 4, 5, 6, 7, 8, 9|...],
R = [1, 10, 100, 10000, 100000].