如何验证Prolog的回溯状态以执行与“懒惰序列"相同的任务.来自Clojure? [英] How to reify Prolog's backtracking state to perform the same task as "lazy seq" from Clojure?

问题描述

这是用Clojure编写的数字的快速排序算法.它基本上是在"Clojure的喜悦" ，第二版，第133页中找到的快速排序算法.我对它进行了少许修改，以期(希望)更好的可读性，因为原始文件感觉太紧凑了:

Here is a quicksort algorithm for numbers written in Clojure. It is basically the quicksort algorithm found in "The Joy of Clojure", 2nd edition, page 133. I modified it slightly for (hopefully) better readability, because the original felt a bit too compact:

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

The algorithm is started by a call to qsort, which envelops a passed list of numbers into another list (thus creating a list containing a single list), then calls 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"，这是一个(对象?事情? thunk ?)，在查询时发出排序序列的下一个数字，即根据需要进行排序.计算状态由(cons oldpivot (qsort-inner rightpartz))
的悬尾给出
• 有一个loop + recur尾递归部分，每当该算法在向左"向左移动排序树时就使用(有关算法的详细信息，请参见下文).
• 有一个完全递归的调用(qsort-inner rightpartz)，当获得下一个最小数字时可以使用该调用，并且可以重新排列"排序树(有关算法的详细信息，请参见下文).

• It delays actual processing. Instead of returning the result of a complete sorting of the input list, it returns a "lazy-seq", which is an (object? thing? thunk?) that emits the next number of the sorted sequence when queried, i.e. sorts on an as-needed basis. The state of the computation is given by the suspended tail of (cons oldpivot (qsort-inner rightpartz))
• There is a loop + recur tail-recursive part which is used whenever the algorithm wanders down the sorting tree "towards the left" (see below for algorithm details.)
• There is a fully recursive call (qsort-inner rightpartz) which is used when the next least number has been obtained and the sorting tree can be "re-arranged" (see below for algorithm details.)

借助lazy-seq的帮助，我们可以使算法一次一发射数据:

With the help of the lazy-seq thing, we can make the algorithm emit data one-by-one:

;; 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中免费提供的！我们可以要求第一个结果，暂停计算，然后通过回溯获得下一个结果.

I was thinking about how to perform this lazy quicksort in Prolog. In fact, laziness, at least in this instance, is given for free in Prolog by backtracking! We can ask for a first result, computation halts and the next result is then obtained by backtracking.

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的最高层时，只能使用这种懒惰".

Unfortunately, the data structure that keeps track of the computational state is not apparent: it is on the stack, it cannot be unified to a variable. Thus is can only use this kind of "laziness" when I am on Prolog's top level.

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

How do I capture the state of the computation and invoke it later?

注意快速排序的工作原理

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

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

The tree structure does not need to be explicitly kept as it holds no information. Instead, the sequence of alternating "leaf lists" and "pivot numbers" is kept in a list. Which is why we the intial "list of a lits of numbers".

推荐答案

Prolog是一种非常实用的语言.只需将您的代码转换为数据即可:

Prolog is a very reifiable language. Just turn your code into data:

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 :

For easier interfacing, we can use 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失败时优雅地关闭输出列表.最初，它是在考虑无限列表的情况下编写的.这留给了敏锐的探险家.

take/4 obviously needs tweaking to close the output list gracefully when next/3 fails. It was written with the infinite lists in mind, originally. This is left as an exercise for a keen explorer.

这篇关于如何验证Prolog的回溯状态以执行与“懒惰序列"相同的任务.来自Clojure?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！