Removing duplicate solutions

Question

My code merges two lists of lists, item by item, in the following way:

mergeL([[a,b],[c,d]], [[1,2],[3,4]], Result). Result = [[a,b,1,2],[c,d,3,4]]

And this is the code i use:

mergeL([],[],[]).
mergeL(List, [], List).
mergeL([], List, List).
mergeL([X|Rest],[Y|Rest2], [XY|Res2]) :-
   mergeL(Rest, Rest2, Res2),
   append(X,Y,XY).

This seems to work but if i call it with two lists of the same size i get three repeated results. Example (both list contain only one element):

?- mergeL([[a,b]],[[1,2,3]],Q).
Q = [[a, b, 1, 2, 3]] ;
Q = [[a, b, 1, 2, 3]] ;
Q = [[a, b, 1, 2, 3]].

Is there a clean way to make this output only one solution?

Answer 1

There are 3 SO-answers already, but I cannot agree with a single one! They all are incorrect.

How to eliminate redundant solutions

Consider the three facts in your definition:

mergeL([],[],[]).
mergeL(List, [], List).
mergeL([], List, List).

They all succeed for mergeL([],[],[]) which is the source of your redundancies. The second and third fact are here for List being a non-empty list. So let us add this to the definition:

mergeL([],[],[]).
mergeL(List, [], List) :- List = [_|_].
mergeL([], List, List) :- List = [_|_].

This eliminates redundant solutions. There is no need for a cut to remove the redundant solutions. The cuts introduced in the other SO-answer, however, may hide solutions. For the query mergeL(Xs,YS,Zs) there is exactly one solution for the cut version, but there should be infinitely many.

How to eliminate leftover choicepoints

Nevertheless, there is some point in using cuts: They are able to remove one choice-point. But such a cut needs to be guarded appropriately like so:

mergeL(Xs, Ys, Zs) :-
   ( Xs == [], Ys == [] -> !
   ; Zs == [] -> !
   ; true
   ),
   Xs = [], Ys = [], Zs = [].
...

I am not sure if this is worth the effort... An implementation might offer this more efficiently. For more details on this see this, and this.

Tail recursiveness

Much more interesting to you is probably a change in the last rule. It should rather read:

mergeL([X|Rest],[Y|Rest2], [XY|Res2]) :-
   append(X,Y,XY),
   mergeL(Rest, Rest2, Res2).

This avoids the temporary allocation of local stack space. So this is definitely an optimization. But an optimization that does not harm the logical reading of your predicate.

On my 2009 32-bit laptop (almost steam-driven) and SWI 6.3.3-40-g064f37b:

Original version:

?- N is 2^20, length(L,N), maplist(=([]),L), time(mergeL(L,L,J)).
% 2,097,206 inferences, 5.232 CPU in 5.250 seconds (100% CPU, 400851 Lips)

Tail recursive version:

?- N is 2^20, length(L,N), maplist(=([]),L), time(mergeL(L,L,J)).
% 2,097,152 inferences, 0.525 CPU in 0.526 seconds (100% CPU, 3997337 Lips)

Th-that is a factor of 10.

And now with longer lists: Tail recursive version:

?- N is 2^22, length(L,N), maplist(=([]),L), time(mergeL(L,L,J)).
% 8,388,608 inferences, 4.228 CPU in 4.237 seconds (100% CPU, 1984272 Lips)

versus the original order:

?- N is 2^22, length(L,N), maplist(=([]),L), time(mergeL(L,L,J)).
% 1,765,930 inferences, 1.029 CPU in 1.033 seconds (100% CPU, 1716119 Lips)
ERROR: Out of local stack

So only 1.7Mi were executed to fill up the local stack. This is primarily a space issue! If you have more memory than I do, simply increase N is 2^22!

Answer 2

A query with the first list empty, i.e., ?-merge([],,), would match the first and the third clause. Likewise, a query with the second list empty would match the first and second clause. That's why you get choicepoints and hence duplicate solutions.

If you place a cut in the body of the first clause, you should be fine:

merge([],[],[]) :- !.

Answer 3

I would commit last choice:

mergeL([X|Rest],[Y|Rest2], [XY|Res2]) :-
    mergeL(Rest, Rest2, Res2), !, append(X,Y,XY).

also @twinterer answer works!

Answer 4

You can add cuts :

mergeL([],[],[]) :- !.
mergeL(List, [], List):- !.
mergeL([], List, List):- !.
mergeL([X|Rest],[Y|Rest2], [XY|Res2]) :-
   mergeL(Rest, Rest2, Res2),
   append(X,Y,XY).