如何具体化 Prolog 的回溯状态以执行与 Clojure 中的“lazy seq”相同的任务？

这是用 Clojure 编写的数字快速排序算法。它基本上是快速排序算法“Clojure 的乐趣”，第 2 版，第 133 页。我稍微修改了它以（希望）更好的可读性，因为原始版本感觉有点太紧凑：

(defn qsort-inner [work]
   (lazy-seq        
      (loop [loopwork work]
         (let [[ part & partz ] loopwork ]
            (if-let [[pivot & valuez] (seq part)]
                  (let [ smaller? #(< % pivot)
                         smz      (filter smaller? valuez)
                         lgz      (remove smaller? valuez)
                         nxxt     (list* smz pivot lgz partz) ]
                        (recur nxxt))
                  (if-let [[oldpivot & rightpartz] partz]
                          (cons oldpivot (qsort-inner rightpartz))
                          []))))))

(defn qsort [ xs ]
   (qsort-inner (list xs)))

该算法通过调用来启动qsort，它将传递的数字列表封装到另一个列表中（从而创建一个包含单个列表的列表），然后调用qsort-inner.

(qsort [10 4 5 88 7 1])     ;; (qsort-inner [[10 4 5 88 7 1]])
;; (1 4 5 7 10 88)

qsort-inner有三点值得关注：

• 它延迟了实际处理。它不返回输入列表的完整排序结果，而是返回一个“lazy-seq”，它是一个 (object? thing?thunk？）在查询时发出排序序列的下一个数字，即根据需要进行排序。计算的状态由悬尾给出(cons oldpivot (qsort-inner rightpartz))
• 有一个loop + recur尾递归部分，每当算法沿着排序树“向左”移动时使用（有关算法详细信息，请参见下文。）
• 有一个完全递归调用(qsort-inner rightpartz)当获得下一个最小数字并且可以“重新排列”排序树时使用它（有关算法详细信息，请参见下文。）

在的帮助下lazy-seq事情，我们可以让算法一一发出数据：

;; the full result is generated on printout
(qsort [10 4 5 88 7 1])
(1 4 5 7 10 88)

;; store the lazy-seq and query it
(def l (qsort [10 4 5 88 7 1]))
(first l)
;; 1
(second l)
;; 4

我正在考虑如何在 Prolog 中执行这种惰性快速排序。事实上，至少在这个例子中，惰性在 Prolog 中是通过回溯免费提供的！我们可以要求第一个结果，计算停止，然后通过回溯获得下一个结果。

qsort_inner(X, [[],X|_]).
qsort_inner(X, [[],_|WorkRest]) :- qsort_inner(X, WorkRest).
qsort_inner(X, [[Piv|Ns]|WorkRest]) :- 
    pick_smaller(Piv,Ns,SMs),
    pick_notsmaller(Piv,Ns,NSMs),
    qsort_inner(X,[SMs,Piv,NSMs|WorkRest]).

pick_smaller(Pivot,Ins,Outs) :- include(@>(Pivot),Ins,Outs).
pick_notsmaller(Pivot,Ins,Outs) :- exclude(@>(Pivot),Ins,Outs).

qsort(X,Lin) :- qsort_inner(X,[Lin]).

“懒惰”地对列表进行排序：

qsort(X,[3,2,1]).
X = 1;
X = 2;
X = 3;
false

必须把它们全部搞定：

qsort_fully(Lin,Lout) :- bagof(X, qsort(X, Lin), Lout).

不幸的是，跟踪计算状态的数据结构并不明显：它位于堆栈上，无法统一为变量。因此只有当我处于Prolog的顶层时才能使用这种“懒惰”。

如何捕获计算的状态并在以后调用它？

注意快速排序的工作原理

• 给定一个数字列表，该算法选择列表的第一个元素作为主元值（图像中的浅绿色）。
• 然后，它构建一棵树，其中包含严格小于“左侧”列表中的主元值的数字、主元本身（深绿色）以及大于或等于“右侧”列表中的主元值的那些数字。
• 然后它递归地沿着这棵树“向左”移动。
• 这一直持续到小于主元值的数字列表为空。
• 此时，主元值（此处为 28）是总体上最小的数字，可以输出。
• 这使得对一个元素进行排序的列表更小。现在可以通过简单的重新排列操作将树减少一级：现在无左分支且无枢轴的“最深树节点，但一个”的右分支成为树节点“最深树节点”的左分支节点只有两个”。
• 现在可以再次“向左”搜索最小元素。

树结构不需要显式保留，因为它不包含任何信息。相反，交替的“叶列表”和“枢轴号”的序列保留在列表中。这就是我们最初的“一列数字列表”的原因。

Prolog 是一种非常可具体化的语言。只需将代码转换为数据即可：

qsort_gen(Lin, G) :- 
    % G is the initial generator state for Lin's quicksorting
    G = qsort_inner([Lin]).

    %    This_State                   Next_Elt      Next_State
next( qsort_inner([[], X    | WorkRest]), X, qsort_inner(WorkRest) ).
next( qsort_inner([[Piv|Ns] | WorkRest]), X, G ) :-
    pick_smaller(  Piv, Ns, SMs),
    pick_notsmaller(Piv, Ns, NSMs),
    next( qsort_inner([SMs, Piv, NSMs | WorkRest]), X, G).

pick_smaller(  Pivot, Ins, Outs) :- include( @>(Pivot), Ins, Outs).
pick_notsmaller(Pivot, Ins, Outs) :- exclude( @>(Pivot), Ins, Outs).

就这样。

15 ?- qsort_gen([3,2,5,1,9,4,8], G), next(G,X,G2), next(G2,X2,G3), next(G3,X3,G4).
G = qsort_inner([[3, 2, 5, 1, 9, 4, 8]]),
X = 1,
G2 = qsort_inner([[], 2, [], 3, [5, 9, 4|...]]),
X2 = 2,
G3 = qsort_inner([[], 3, [5, 9, 4, 8]]),
X3 = 3,
G4 = qsort_inner([[5, 9, 4, 8]]).

16 ?- qsort_gen([1,9,4,8], G), next(G,X,G2), next(G2,X2,G3), next(G3,X3,G4).
G = qsort_inner([[1, 9, 4, 8]]),
X = 1,
G2 = qsort_inner([[9, 4, 8]]),
X2 = 4,
G3 = qsort_inner([[8], 9, []]),
X3 = 8,
G4 = qsort_inner([[], 9, []]).

17 ?- qsort_gen([1,9,4], G), next(G,X,G2), next(G2,X2,G3), next(G3,X3,G4).
G = qsort_inner([[1, 9, 4]]),
X = 1,
G2 = qsort_inner([[9, 4]]),
X2 = 4,
G3 = qsort_inner([[], 9, []]),
X3 = 9,
G4 = qsort_inner([[]]).

为了更方便地连接，我们可以使用take/4:

take( 0, Next, Z-Z, Next):- !.
take( N, Next, [A|B]-Z, NextZ):- N>0, !, next( Next, A, Next1),
  N1 is N-1,
  take( N1, Next1, B-Z, NextZ).

Then,

19 ?- qsort_gen([3,2,5,1,9,4,8], G), take(6, G, L-[], _).
G = qsort_inner([[3, 2, 5, 1, 9, 4, 8]]),
L = [1, 2, 3, 4, 5, 8].

20 ?- qsort_gen([3,2,5,1,9,4,8], G), take(7, G, L-[], _).
G = qsort_inner([[3, 2, 5, 1, 9, 4, 8]]),
L = [1, 2, 3, 4, 5, 8, 9].

21 ?- qsort_gen([3,2,5,1,9,4,8], G), take(10, G, L-[], _).
false.

take/4显然需要调整以在以下情况下优雅地关闭输出列表：next/3失败了。最初，它是在考虑无限列表的情况下编写的。这是留给敏锐的探索者的练习。