Why does my Prolog predicate succeed twice with the same binding?

Question

Sorry if this is a dumb question, but I'm still at the early stages of learning Prolog (SWI-Prolog in case it makes a difference), and probably doing something stupid.

I'm trying to write a predicate weave/3 that will succeed if the third parameter (list) is the same as if you wove the first two together[*]. For example...

weave([1], [a], [1,a]).
weave([1,2], [a,b], [1,a,2,b]).
weave([1,2], [a,b,c,d], [1,a,2,b]).

My intention is that if one list is longer than the other (as in the third example), the extra elements are ignored.

My current attempt at this is as follows...

weave(_, [], []). % bail out if the first list is longer
weave([], _, []). % bail out if the second list is longer
weave([H1|T1], [H2|T2], Res) :-
  weave(T1, T2, Ts),
  append([H1, H2], Ts, Res).

This works fine when the second list is longer than the first...

weave([1,2], [a,b,c,d,e,f], Res).
Res = [1, a, 2, b].

I get the one binding shown, and the execution ends.

If the first list is longer, I still get the correct binding, but need to press the ; key and get false for execution to end...

weave([1,2,3,4], [a,b,c], Res).
Res = [1, a, 2, b, 3, c] ;
false.

However, if the lists are the same length, then I get the correct binding, but twice, meaning that after the first one is shown, I press the ; key, and get the same binding. I don't need to press ; in this case...

weave([1,2,3], [a,b,c], Res).                             
Res = [1, a, 2, b, 3, c] ;
Res = [1, a, 2, b, 3, c].

Anyone able to explain what's going on here. Thanks

[*] Not sure if such a predicate already exists, but even if it does, my intention is to learn the language, so writing my own versions of built-in predicates is very useful, even if I only ever use the built-in (and presumably more robust and efficient) ones.

Answer 1

Here's a nice method:

weave([], _, []).
weave([H|T], L, W) :-
    weave_l_(L, T, H, W).

weave_l_([], _T, _H, []).
weave_l_([LH|LT], T, H, [H, LH|W]) :-
    weave(T, LT, W).

This is using first-argument indexing to avoid unwanted choicepoints, i.e. [] vs [Head|Tail].

Results in swi-prolog:

?- weave([1], [a], W).
W = [1, a].

?- weave([1,2], [a,b], W).
W = [1, a, 2, b].

?- weave([1,2], [a,b,c,d], W).
W = [1, a, 2, b].

?- weave([1,2,3], [a,b,c], W). 
W = [1, a, 2, b, 3, c].

When at an unwanted choicepoint, press asterisk (i.e. Shift+8) for swi-prolog to show an explanation.

Answer 2

weave(_, [], []). % bail out if the first list is longer
weave([], _, []). % bail out if the second list is longer

These aren't bailing out exactly, they are succeeding and leaving choicepoints, and they aren't doing it if the blank position is longer, they're doing it whatever the blank position is.

Particularly if it's also an empty list then weave([], [], []). succeeds for both of those rules, and that's how input lists of the same length end up, giving you the double solution. One quick option is:

weave([], [], []).
weave( L, [], []) :- dif(L, []).  % succeed if L is not empty.
weave([],  R, []) :- dif(R, []).  % same for R. Not weaving the remainder.

weave([H1|T1], [H2|T2], Res) :-
  weave(T1, T2, Ts),
  append([H1, H2], Ts, Res).

Edit: here's another version which leaves fewer choicepoints:

weave([], _, []).
weave([LH|LT], R, [LH|Res]) :-
    weave(R, LT, Res).