我正在嘗試在 prolog 中實作歸并排序（樹莓派上的 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 = []
如果有人在該語言方面更有經驗，知道無限回圈的來源，請告訴我，謝謝。
uj5u.com熱心網友回復：
合并排序的第三個子句將匹配前兩個子句。您可以 cut( !) 前兩個子句或模式匹配第三個子句以確保至少有兩個元素。
mergesort(Lst, SortedLst) :-
Lst = [_, _ | _],
...
將其寫為mergesort([X, Y | Xs], SortedList)然后分配可能更好Lst = [X, Y | Xs]。子句索引可能重要或不重要。
或者
mergesort([], []) :- !.
mergesort([Only], [Only]) :- !.
除非您正在尋找謂詞的多種解決方案，否則請嘗試確保只有一個子句頭部與任何輸入匹配。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/403066.html
標籤：
上一篇：Lua遞回問題出乎意料的結果