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

查看：15
本文介绍了如何具体化 Prolog 的回溯状态以执行与“lazy seq"相同的任务?来自 Clojure?的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！

问题描述

这是一个用 Clojure 编写的数字快速排序算法.它基本上是 "The Joy of Clojure"，第 2 版，第 133 页中的快速排序算法.我稍微修改了它以(希望)更好的可读性，因为原始感觉有点太紧凑了:p>

(defn qsort-inner [工作](惰性序列(循环[循环工作](让 [[ part & partz ] loopwork ](if-let [[pivot & valuez] (seq part)](让 [ 更小?#(< % pivot)smz(过滤器更小?valuez)lgz(去掉更小的?valuez)nxxt (list* smz pivot lgz partz) ](重复nxxt))(if-let [[oldpivot & rightpartz] partz](缺点 oldpivot(qsort-inner rightpartz))[]))))))(定义 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?

    解决方案

    Prolog 是一种非常可具体化的语言.只需将您的代码转化为数据:

    qsort_gen(Lin, G) :-% G 是 Lin 快速排序的初始生成器状态G = qsort_inner([林]).% This_State Next_Elt Next_State下一个(qsort_inner([[]，X | WorkRest])，X，qsort_inner(WorkRest)).下一个(qsort_inner([[Piv|Ns] | WorkRest])，X，G):-pick_smaller(Piv, Ns, SMs),pick_notsmaller(Piv, Ns, NSMs),下一个(qsort_inner([SMs，Piv，NSMs | WorkRest])，X，G).pick_smaller(Pivot, Ins, Outs) :- 包括(@>(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)，下一个(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)，下一个(G，X，G2)，下一个(G2，X2，G3)，下一个(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):- !.采取( N, Next, [A|B]-Z, NextZ):- N>0, !, next( Next, A, Next1),N1 是 N-1，采取(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-[], _).错误的.

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

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

    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 has three noteworthy points:

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

    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

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

    Sort a list "lazily":

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

    Gotta get them all:

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

    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?

    Note on how the quick sort works

    • Given a list of numbers, the algorithm selects the first element of the list as pivot value (light green in the image).
    • It then builds a tree with those numbers strictly smaller than the pivot value in a list "on the left", the pivot itself (dark green) and those numbers larger or equal to the pivot value as a list "on the right".
    • It then recursively moves down this tree "towards the left".
    • This continues until the list of numbers smaller than the pivot value is empty.
    • At that point, the pivot value (here, 28) is the least number overall and can be output.
    • This makes the list to sort one element smaller. The tree can now be reduced by one level with a trivial rearrangement operation: the right branch of the now left-branch-less and pivot-less "deepest tree-node but one" becomes the left branch of the tree node "deepest tree-node but two".
    • Searching for the least element can now proceed again "towards the left".

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

    That's all.

    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([[]]).

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

    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 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 的回溯状态以执行与“lazy seq"相同的任务?来自 Clojure?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！

查看全文
相关文章
其他开发最新文章
热门教程
热门工具
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆