序言中的合并排序 - 无限递归？

Question

我正在尝试在 prolog 中实现合并排序（raspberry pi 上的 swi prolog）。我对这门语言很陌生，我在这里拥有的基本上是我的 Haskell 尽我所能将版本“移植”到 Prolog：

:- 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).

运行这段代码似乎正确地执行了排序，但后来螺旋上升到无限和超越：

?- 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|...]

我爬过调试器（跟踪模式），没有找到任何线索

   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|...] ;

我用一个空列表又试了一次，这次是调试器显示正在调用“合并”，这种情况不应该发生。

?- 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 = []

如果有更熟悉该语言的人知道无限循环在哪里来自哪里，请告知，谢谢

Answer 1

您的合并排序的第三个子句将与前两个子句匹配。您可以剪切（!）前两个子句或模式匹配第三个以确保至少两个元素。

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

最好写成mergesort([X, Y | Xs], SortedList)然后赋值Lst = [X, Y | Xs]。子句索引是否重要。

或

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

除非您正在寻找谓词的多个解决方案，否则请尝试确保只有一个子句的头部匹配任何输入。

序言中的合并排序 - 无限递归？

mergesort in prolog - infinite recursion?

recursion

mergesort

prolog

infinite