Prolog Program Not Merging Sorted Lists Correctly

Question

I have a simple program I'm trying to write in Prolog. Essentially, as I learning exercise, I'm trying to write a program that takes two sorted lists as input, and returns the merged list that is also sorted. I have dubbed the predicate "merge2" as to no be confused with the included predicate "merge" that seems to do this already.

I am using recursion. My implementation is below

merge2([],[],[]).
merge2([X],[],[X]).
merge2([],[Y],[Y]).
merge2([X|List1],[Y|List2],[X|List]):- X =< Y,merge2(List1,[Y|List2],List).
merge2([X|List1],[Y|List2],[Y|List]):- merge2([X|List1],List2,List).

When I run this, I get X = [1,2,4,5,3,6] which is obviously incorrect. I've been able to code multiple times and tried to draw out the recursion. To the best of my knowledge, this should be returning the correct result. I'm not sure why the actualy result is so strange.

Thank you.

Answer 1

This is done using difference list and since you are learning it uses reveals, AKA spoiler, which are the empty boxes that you have to mouse over to ravel the contents. Note that the reveals don't allow for nice formatting of code. At the end is the final version of the code with nice formatting but not hidden by a reveal so don't peek at the visible code at the very end if you want to try it for yourself.

This answer takes it that you have read my Difference List wiki.

Your basic idea was sound and the basis for this answer using difference list. So obviously the big change is to just change from closed list to open list.

As your code is recursive, the base case can be used to set up the pattern for the rest of the clauses in the predicate.

Your simplest base case is

merge2([],[],[]).

but a predicate using difference list can use various means to represent a difference list with the use of L-H being very common but not one I chose to use. Instead this answer will follow the pattern in the wiki of using two variables, the first for the open list and the second for the hole at the end of the open list.

Try to create the simple base case on your own.

merge2_prime([],[],Hole,Hole).

Next is needed the two base cases when one of the list is empty.

merge2_prime([X],[],Hole0,Hole) :-
Hole0 = [X|Hole].
merge2_prime([],[Y],Hole0,Hole) :-
Hole0 = [Y|Hole].

Then the cases that select an item from one or the other list.

merge2_prime([X|List1],[Y|List2],Hole0,Hole) :-
X =< Y,
Hole0 = [X|Hole1],
merge2_prime(List1,[Y|List2],Hole1,Hole).
merge2_prime(List1,[Y|List2],Hole0,Hole) :-
Hole0 = [Y|Hole1],
merge2_prime(List1,List2,Hole1,Hole).

Lastly a helper predicate is needed so that the query merge2(L1,L2,L3) can be used.

merge2(L1,L2,L3) :-
merge2_prime(L1,L2,Hole0,Hole),
Hole = [],
L3 = Hole0.

If you run the code as listed it will produce multiple answer because of backtracking. A few cuts will solve the problem.

merge2(L1,L2,L3) :-
    merge2_prime(L1,L2,Hole0,Hole),
    Hole = [],
    L3 = Hole0.
merge2_prime([],[],Hole,Hole) :- !.
merge2_prime([X],[],Hole0,Hole) :-
    !,
    Hole0 = [X|Hole].
merge2_prime([],[Y],Hole0,Hole) :-
    !,
    Hole0 = [Y|Hole].
merge2_prime([X|List1],[Y|List2],Hole0,Hole) :-
    X =< Y,
    !,
    Hole0 = [X|Hole1],
    merge2_prime(List1,[Y|List2],Hole1,Hole).
merge2_prime(List1,[Y|List2],Hole0,Hole) :-
    Hole0 = [Y|Hole1],
    merge2_prime(List1,List2,Hole1,Hole).

Example run:

?- merge2([1,3,4],[2,5,6],L).
L = [1, 2, 3, 4, 5, 6].

?- merge2([0],[0],L).
L = [0, 0].

I didn't check this with lots of examples as this was just to demonstrate that an answer can be found using difference list.

Answer 2

QuickCheck is your friend. In this case, the property that you want to verify can be expressed using the following predicate:

sorted(L1, L2) :-
    sort(L1, S1),
    sort(L2, S2), 
    merge2(S1, S2, L),
    sort(L, S),
    L == S.

Note that sort/2 is a standard Prolog built-in predicate. Using the QuickCheck implementation provided by Logtalk's lgtunit tool, which you can run using most Prolog systems, we get:

?- lgtunit::quick_check(sorted(+list(integer),+list(integer))).
*     quick check test failure (at test 2 after 0 shrinks):
*       sorted([0],[0])
false.

I.e. you code fails for L1 = [0] and L2 = [0]:

?- merge2([0], [0], L).
L = [0, 0] ;
L = [0, 0] ;
false.

Tracing this specific query should allow you to quickly find at least one of the bugs in your merge2/4 predicate definition. In most Prolog systems, you can simply type:

?- trace, merge2([0], [0], L).

If you want to keep duplicates in the merged list, you can use the de facto standard predicates msort/2 in the definition of the property:

sorted(L1, L2) :-
    sort(L1, S1),
    sort(L2, S2), 
    merge2(S1, S2, L),
    msort(L, S),
    L == S.

In this case, running QuickCheck again:

?- lgtunit::quick_check(sorted(+list(integer),+list(integer))).
*     quick check test failure (at test 3 after 8 shrinks):
*       sorted([],[475,768,402])
false.

This failure is more informative if you compare the query with your clauses that handle the case where the first list is empty...