Prolog/排序
排序是許多程式中的基本任務。我們解釋如何在 Prolog 中編寫快速且通用的歸併排序演算法的實現。
歸併排序演算法如下所示
function merge_sort(m)
if length(m) ≤ 1
return m
else
left, right = split_in_half(m)
left = merge_sort(left)
right = merge_sort(right)
result = merge(left, right)
return result
在 Prolog 中實現以這種風格呈現的任何演算法，我們首先要做的是將其從函式語言轉換為謂詞語言。回想一下 Prolog 沒有return構造，但我們可以使用未繫結的變數作為輸出機制。因此，我們將編寫一個謂詞mergesort(Xs, S)，它給定一個列表Xs，將“返回”一個排序的變體，方法是將S繫結到它。
演算法中的 if-then-else 結構呢？我們可以直接翻譯它，但我們也可以選擇使用 Prolog 的模式匹配。因為條件檢查 ≤1，所以我們有三個結構性情況：空列表、一個元素的列表以及 catch-all 情況。因此，讓我們編寫第一個歸併排序。
% the empty list must be "returned" as-is
mergesort([], []).
% same for single element lists
mergesort([X], [X]).
% and now for the catch-all:
mergesort([X|Xs], S) :-
length(Xs, Len),
0 < Len,
split_in_half([X|Xs], Ys, Zs),
mergesort(Ys, SY),
mergesort(Zs, SZ),
merge(SY, SZ, S).
這是演算法的骨架。我們省略了輔助謂詞的定義split_in_half和merge，但對於一個功能齊全的排序謂詞，我們當然也必須定義它們。讓我們從merge開始，它接受兩個排序列表並生成一個新的排序列表，其中包含它們的全部元素。我們使用 Prolog 的遞迴和模式匹配來實現merge.
% First two cases: merging any list Xs with an empty list yields Xs
merge([], Xs, Xs).
merge(Xs, [], Xs).
% Other cases: the @=< predicate compares terms by the "standard order"
merge([X|Xs], [Y|Ys], [X|S]) :-
X @=< Y,
merge(Xs, [Y|Ys], S).
merge([X|Xs], [Y|Ys], [Y|S]) :-
Y @=< X,
merge([X|Xs], Ys, S).
這個謂詞可以工作，但它很重複，效率不高。我們將在稍後重新討論它，但首先我們必須定義split_in_half，它將列表分成兩個大小大致相等的列表（大致因為它可能包含奇數個元素）。為此，我們需要列表的長度，但我們不幸的是沒有將其作為輸入（見merge_sort），因此我們需要計算它。我們使用輔助謂詞split_at在計算長度後實際拆分列表。
split_in_half(Xs, Ys, Zs) :-
length(Xs, Len),
Half is Len // 2, % // denotes integer division, rounding down
split_at(Xs, Half, Ys, Zs).
練習。在繼續定義之前split_at，嘗試自己實現它。使用遞迴和對輸入列表和第二個長度引數進行案例匹配。
好了，現在開始split_at:
% split_at(Xs, N, Ys, Zs) divides Xs into a list Ys of length N
% and a list Zs containing the part after the first N.
split_at(Xs, N, Ys, Zs) :-
length(Ys, N),
append(Ys, Zs, Xs).
如果split_at的定義看起來很神奇，那麼嘗試以宣告的方式閱讀它：“一個列表Xs，在其前N個元素後拆分為Ys和Zs，意味著Ys的長度為N和Ys和Zs可以追加以檢索Xs。”這個方法起作用的事實是 Prolog 的“雙向”能力的一個例子：許多謂詞可以在“反向順序”執行以獲得計算的逆運算。
現在我們有了可以對任何列表進行排序的歸併排序程式，但它的一些部分並不特別優雅。讓我們首先重新審視merge_sort。我們翻譯了一個 if-then-else 結構到多個子句中，因為這在 Prolog 中很常見，但實際上我們沒有理由這樣做：該演算法是確定性的，所以不應該有任何回溯發生。讓我們嘗試使用 Prolog 自己的 if-then-else 對虛擬碼進行更直接的重寫。
mergesort(Xs, S) :-
length(Xs, Len),
(Len =< 2 ->
S = Xs
;
split_in_half(Xs, Ys, Zs),
mergesort(Ys, SY),
mergesort(Zs, SZ),
merge(SY, SZ, S)
).
現在，讓我們解決merge的效率和可讀性，就像承諾的那樣。這個謂詞的最後兩個情況看起來像複製貼上，這始終是一個程式碼異味。此外，可能發生了不必要的回溯。讓我們使用 if-then-else 重寫merge。
% First two cases: merging any list Xs with an empty list yields Xs
merge([], Xs, Xs).
merge(Xs, [], Xs).
% Other cases: the @=< predicate compares terms by the "standard order"
merge(Xs, Ys, S) :-
Xs = [X|Xs0],
Ys = [Y|Ys0],
(X @=< Y ->
S = [X|S0],
merge(Xs0, Ys, S0)
;
S = [Y|S0],
merge(Xs, Ys0, S0)
).