CODEWITHSUNDEEP
listsortingmergeprolog
user1666419
user1666419

Reputation: 77

How to make one sorted list out of two already sorted lists

In Prolog I have to figure out a way how to combine two already sorted lists into one sorted list. So in other words: from 2 lists I have to compare the heads and add the smallest to a new list. I think I've gotten pretty far, but somehow it just doesn't work and I can't figure out why not. I don't get any errors BTW. It just gives false back.

So, I hope someone can tell me what I'm doing wrong.

sort([],L,L).
sort(L,[],L).
sort([Head1|Tail1],[Head2|Tail2],L) :- 
    Head1 < Head2 -> append([Head1],L,L2), sort(Tail1,[Head2|Tail2],L2) ; 
    Head1 > Head2 -> append([Head2],L,L2), sort([Head1|Tail1],Tail2,L2) ; 
    Head1 == Head2 -> append([Head1],L,L2), append([Head2],L2,L3), 
                                            sort(Tail1,Tail2,L3).

Upvotes: 3

Views: 5705

Answers (3)

repeat
repeat

Reputation: 18726

Telling from the code in your question, you are merging sorted lists of numbers. If these numbers are all integers and if your Prolog system offers , consider using code presented here. Why?

  • The implementation preserves .
  • The code is monotone, making it robust and flexible: always get logically sound answers, even when working for non-ground data.
  • The main predicate sorted1_sorted2_merged/3 behaves like a real relation.
  • Unlike the builtin sort/2, this code keeps all duplicates (in exactly the same multiplicities).
  • Regarding equal items in the lists to be merged, it behaves reasonable: Items in input #1 that are equal to some items in input #2 precede those in the merged result.
  • The implementation is efficient in the sense that it does not leave useless choicepoints with goals like sorted1_sorted2_merged([1,3,5],[2,4,5,6],Zs).

Without any further ado... here's the code:

:- use_module(library(clpfd)).

sorted1_sorted2_merged([]    ,Ys,Ys).
sorted1_sorted2_merged([X|Xs],Ys,Zs) :-
   sorted2_hd1_tl1_merged(Ys,X,Xs,Zs).

hd1_tl1_hd2_tl2_merged(X,Xs,Y,Ys,Zs) :-
   zcompare(Op,X,Y),
   op_hd1_tl1_hd2_tl2_merged(Op,X,Xs,Y,Ys,Zs).

sorted1_hd2_tl2_merged([]    ,Y,Ys,[Y|Ys]).
sorted1_hd2_tl2_merged([X|Xs],Y,Ys,Zs) :- 
   hd1_tl1_hd2_tl2_merged(X,Xs,Y,Ys,Zs).

sorted2_hd1_tl1_merged([]    ,X,Xs,[X|Xs]).
sorted2_hd1_tl1_merged([Y|Ys],X,Xs,Zs) :-
   hd1_tl1_hd2_tl2_merged(X,Xs,Y,Ys,Zs).

op_hd1_tl1_hd2_tl2_merged(<,X,Xs,Y,Ys,[X|Zs]) :-
   sorted1_hd2_tl2_merged(Xs,Y,Ys,Zs).
op_hd1_tl1_hd2_tl2_merged(=,X,Xs,Y,Ys,[X|Zs]) :- 
   sorted1_hd2_tl2_merged(Xs,Y,Ys,Zs).
op_hd1_tl1_hd2_tl2_merged(>,X,Xs,Y,Ys,[Y|Zs]) :- 
   sorted1_hd2_tl2_merged(Ys,X,Xs,Zs).

On to some queries! First:

?- sorted1_sorted2_merged([1,3,4,6],[2,4,5,5,7],Xs).
Xs = [1,2,3,4,4,5,5,6,7].         % succeeds deterministically

Does it work in the "other directions", too?

?- sorted1_sorted2_merged([1,3,4,6],Ys,[1,2,3,4,4,5,5,6,7]).
Ys = [2,4,5,5,7] ;                % succeeds, but leaves behind choicepoint
false.

?- sorted1_sorted2_merged(Xs,[2,4,5,5,7],[1,2,3,4,4,5,5,6,7]).
Xs = [1,3,4,6] ;                  % succeeds, but leaves behind choicepoint
false.

At last, a quite general use:

?- sorted1_sorted2_merged(Xs,Ys,[0,1,2,3]).
Xs = [       ], Ys = [0,1,2,3] ;
Xs = [0,1,2,3], Ys = [       ] ;
Xs = [0      ], Ys = [  1,2,3] ;
Xs = [0,1    ], Ys = [    2,3] ;
Xs = [0,1,2  ], Ys = [      3] ;
Xs = [0,1,  3], Ys = [      2] ;
Xs = [0,  2,3], Ys = [      1] ;
Xs = [0,    3], Ys = [  1,2  ] ;
Xs = [0,  2  ], Ys = [  1,  3] ;
Xs = [  1,2,3], Ys = [0      ] ;
Xs = [    2,3], Ys = [0,1    ] ;
Xs = [      3], Ys = [0,1,2  ] ;
Xs = [    2  ], Ys = [0,1,  3] ;
Xs = [  1    ], Ys = [0,  2,3] ;
Xs = [  1,2  ], Ys = [0,    3] ;
Xs = [  1,  3], Ys = [0,  2  ] ;
false.

Upvotes: 1

CapelliC
CapelliC

Reputation: 60034

You should simplify your code a bit:

sort([],L,L).
sort(L,[],L).
sort([Head1|Tail1], [Head2|Tail2], L) :- 
    Head1 < Head2 -> L = [Head1|R], sort(Tail1,[Head2|Tail2],R) ;
    Head1 > Head2 -> L = [Head2|R], sort([Head1|Tail1],Tail2,R) ;
    L = [Head1,Head2|R], sort(Tail1,Tail2,R).

test:

?- sort([1,2,4,5,18],[1,3,5,10],R).
R = [1, 2, 3, 4, 5, 10, 18] .

Naming such predicate sort is really misleading, merge would be much better....

edit L = [Head1,Head2|R] instead of L = [Head1|R] where Head1=Head2 (having failed the previous tests) departs from sort/2 Prolog semantic, that removes duplicates.

Upvotes: 4

Will Ness
Will Ness

Reputation: 71109

In SWI Prolog there's merge/3 built-in predicate that does exactly that. So you shouldn't call your predicate "sort"; it's not. It's "merge".

Next, let's read your definition.

merge([H1|T1], [H2|T2], L) :-

means, merging the two lists produces the merged list L. So far, so good.

    H1 < H2 -> append([H1],L,L2), merge(T1,[H2|T2],L2)

means, in case H1 < H2, prefixing the answer list L with H1 gives L2, which is the result of merging ... Wait, what? Does that make sense?

Prolog is not Basic. What we write are not "commands" to "do" stuff (well, they are, but in a roundabout way). If we want to say that H1 is the head element of L, we say it:

               L = [H1|L2],        merge(T1,[H2|T2],L2) 
        %% or: append([H1],L2,L),

etc. Now this makes sense. :)

Upvotes: 2

Related Questions