mergesort in prolog - infinite recursion?-CodePudding

I am attempting to implement mergesort in prolog (swi prolog on raspberry pi). I'm very new to the language and what I have here is basically my Haskell version "ported" to Prolog as best I could:

:- use_module(library(list_util), [split_at/4, take/3, drop/3]).

merge([], [], []).
merge(Lst, [], Lst).
merge([], Lst, Lst).
merge([X|XS], [Y|YS], MergedLst) :- X < Y, MergedLst = [X|MergedLst2], merge(XS, [Y|YS], MergedLst2).
merge([X|XS], [Y|YS], MergedLst) :- X >= Y, MergedLst = [Y|MergedLst2], merge([X|XS], YS, MergedLst2).


mergesort([], []).
mergesort([Only], [Only]).
mergesort(Lst, SortedLst) :-
  length(Lst, LstLen),
  HalfWay is truncate(LstLen / 2),
  take(HalfWay, Lst, FirstHalf),
  drop(HalfWay, Lst, SecondHalf),
  mergesort(FirstHalf, A),
  mergesort(SecondHalf, B),
  merge(A, B, SortedLst).

Running this code appears to perform the sort correctly, but then goes spiraling into infinite and beyond:

?- mergesort([1,6,3,10,4,9,2,4,7,3], Y).
Y = [1, 2, 3, 3, 4, 4, 6, 7, 9|...] ;
Y = [1, 2, 3, 3, 4, 4, 6, 7, 9|...] ;
Y = [1, 2, 3, 3, 4, 4, 6, 7, 9|...]

I creeped through the debugger (trace mode) and didn't find any clues

   Call: (18) merge([10], [], _5322) ? creep
   Exit: (18) merge([10], [], [10]) ? creep
   Exit: (17) merge([10], [9], [9, 10]) ? creep
   Exit: (16) merge([10], [7, 9], [7, 9, 10]) ? creep
   Exit: (15) merge([6, 10], [7, 9], [6, 7, 9, 10]) ? creep
   Exit: (14) merge([4, 6, 10], [7, 9], [4, 6, 7, 9, 10]) ? creep
   Exit: (13) merge([4, 6, 10], [4, 7, 9], [4, 4, 6, 7, 9, 10]) ? creep
   Exit: (12) merge([3, 4, 6, 10], [4, 7, 9], [3, 4, 4, 6, 7, 9, 10]) ? creep
   Exit: (11) merge([3, 4, 6, 10], [3, 4, 7, 9], [3, 3, 4, 4, 6, 7, 9, 10]) ? creep
   Exit: (10) merge([3, 4, 6, 10], [2, 3, 4, 7, 9], [2, 3, 3, 4, 4, 6, 7, 9|...]) ? creep
   Exit: (9) merge([1, 3, 4, 6, 10], [2, 3, 4, 7, 9], [1, 2, 3, 3, 4, 4, 6, 7|...]) ? creep
   Exit: (8) mergesort([1, 6, 3, 10, 4, 9, 2, 4|...], [1, 2, 3, 3, 4, 4, 6, 7|...]) ? creep
Y = [1, 2, 3, 3, 4, 4, 6, 7, 9|...] ;

I tried it again with an empty list and this time the debugger reveals that "merge" is being called, which shouldn't be happening for that case.

?- mergesort([], Y).
Y = [] ;
Y = [] ;
Y = []
Action (h for help) ? trace
continue (trace mode)
; [trace]
   Redo: (9) merge([], [], _3038) ? creep
   Exit: (9) merge([], [], []) ? creep
   Exit: (8) mergesort([], []) ? creep
Y = []

If anyone more experienced in the language knows where the infinite loop is coming from, please let me know, thank you.

CodePudding user response：

Your third clause of mergesort will match previous two clauses. You can cut(!) the first two clauses or pattern match the third to ensure atleast two elements.

mergesort(Lst, SortedLst) :-
    Lst = [_, _ | _],
    ...

Probably better to write it as mergesort([X, Y | Xs], SortedList) and then assign Lst = [X, Y | Xs]. Clause indexing might matter or not.

mergesort([], []) :- !.
mergesort([Only], [Only]) :- !.

Unless you are looking for multiple solutions to the predicate, try to make sure only one head of the clauses match any input.