如何验证Prolog的回溯状态以执行与Clojure中的“懒惰序列”相同的任务？

Question

这是用Clojure编写的数字的快速排序算法。它基本上是在“ The Clojure的喜悦”第二版（第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”，这是一个（对象？事物？笨拙？），在查询时会发出下一个排序序列号，即按根据需要。计算的状态由(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）是总数最少的数字，可以输出。
• 这使排序一个元素的列表变小。现在可以通过简单的重新排列操作将树减少一级：现在左分支少且无枢轴的“最深树节点，但一个”的右分支成为树节点“最深树-节点，但两个”。
• 现在，搜索最小的元素可以再次“向左”进行。

树形结构不需要显式保留，因为它不包含任何信息。而是将交替的“叶列表”和“枢轴编号”的序列保留在列表中。这就是为什么我们最初使用“一连串数字”。

Answer 1

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

然后，

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失败时需要进行调整以优雅地关闭输出列表。最初，它是在考虑无限列表的情况下编写的。这留给了敏锐的探险家。