1

I must write predicate which will split one list into two lists (on halve):

halve(X-Y, X-Z, Z-Y) :- halve_pom(X-Y, X-Y, Z), !.

halve_pom(Z-Y, Y-Y, Z).

halve_pom([_|A]-Y, [_,_|B]-Y, Z) :- halve_pom(A-Y, B-Y, Z).

That was easy, but now I must write algorithm which will do mergesort - I don't have any idea. This algorithm must use difference lists.

Please help.

Will Ness
  • 70,110
  • 9
  • 98
  • 181
Jacob
  • 799
  • 1
  • 6
  • 12

1 Answers1

1

No, it was not "easy", as it doesn't work, unfortunately. halve([1,2,3]-[],A,B) doesn't work; halve_pom([1,2,3]-[],A,B) doesn't work either. Also, it is unclear which of the splitting schemes you prefer, [1,2,3,4,5,6,7] -> ([1,3,5,7] , [2,4,6]) or -> ([1,2,3,4] , [5,6,7]).

If your halve predicate worked, all you'd have left to do is to define merge, which would merge the two halves of a list, in order. Then,

mergesort(A,S):- halve(A,B-[],C-[]), mergesort(B,SB), mergesort(C,SC),
  merge(SB,SC,S-[]).

Note that you probably would call it with a normal list A, i.e. the halve predicate should expect its first argument as a normal list (i.e. not a difference-list).

See also What does the "-" symbol mean in Prolog when dealing with lists? . The '-' is unnecessary; instead, its two constituents should be used as two separate arguments to a predicate.

So, one way to code halve is

halve([A,B|C],[A|X]-ZX,[B|Y]-ZY):- halve(C,X-ZX,Y-ZY). 
halve([A],[A|X]-X,Y-Y). 
halve([],X-X,Y-Y).

The same approach can be used to code merge:

merge(SB,SC,S-Z):- SB=[A|B], SC=[C|D], A=<C, S=[A|T], merge(B,SC,T-Z).
merge(SB,SC,S-Z):- SB=[A|B], SC=[C|D], A>C,  ... ,    ... .
merge(SB,SC,S-Z):- SB=[A|B], SC=[],          ... ,    ... .
merge(SB,SC,S-Z):- SB=[], SC=[C|D],          S=[C|T], ... .
merge([],[],Z-Z).
Community
  • 1
  • 1
Will Ness
  • 70,110
  • 9
  • 98
  • 181
  • For my edification could you show how to do `halve/3` with difference lists, using the odd/even splitting scheme? I'd greatly appreciate it. – Daniel Lyons Mar 27 '13 at 15:14
  • Thanks. :) I "get" DLs in a vague, conceptual way, but apparently not well enough to actually use them. – Daniel Lyons Mar 27 '13 at 15:16
  • @DanielLyons I think that's it. Good that you asked, turned out I had to fix it a bit. see also http://en.wikipedia.org/wiki/Tail_recursion_modulo_cons#Tail_recursion_modulo_cons – Will Ness Mar 27 '13 at 15:25
  • @DanielLyons Glad to help. Instead, let me just up-vote your comment; feels as good. :) This stuff is made unnecessarily hard by using too vague a language, in the books. Just call them "open-ended lists" and all is simple and clear! – Will Ness Mar 27 '13 at 15:36
  • I have come up with a solution using flip/flopping accumulators instead of three cases: `halve([], X-X, Y-Y). halve([A|C], [A|X]-ZX, Y-ZY) :- halve(C, Y-ZY, X-ZX).`. I'd like to have your feedback on it if you have a minute to take a look. – Daniel Lyons Mar 27 '13 at 19:19
  • @DanielLyons ah, very nice, the rotating accumulators! :) It extends to three-way partitions too: `three([], X-X, Y-Y, Z-Z). three([A|B], [A|X]-ZX, Y-ZY, Z-ZZ) :- three(B, Y-ZY, Z-ZZ, X-ZX).` I first saw something like that in [a post by ed'ka in F# tag](http://stackoverflow.com/a/7945580/849891). Translates to Haskell too. `threeWay xs = foldr (\x (b,c,a)->(x:a,b,c)) ([],[],[]) xs`. In Prolog it is much simpler. :) – Will Ness Mar 27 '13 at 19:49
  • let us [continue this discussion in chat](http://chat.stackoverflow.com/rooms/27037/discussion-between-will-ness-and-daniel-lyons) – Will Ness Mar 27 '13 at 19:54