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