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

Question

这是一个用 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 ?)，它在查询时发出排序序列的下一个数字，即 sorts根据需要。计算状态由 (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 时，显然需要调整以优雅地关闭输出列表失败。它最初是在考虑无限列表的情况下编写的。这留给敏锐的探索者练习。