Как преобразовать состояние возврата Prolog для выполнения той же задачи, что и lazy seq из Clojure?

Вот алгоритм быстрой сортировки чисел, написанных на Clojure. По сути, это алгоритм быстрой сортировки из "The Joy of 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 бесплатно путем возврата! Мы можем запросить первый результат, вычисление останавливается, а следующий результат получается с помощью поиска с возвратом.

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) является наименьшим числом в целом и может быть выведено.
• Это делает список для сортировки на один элемент меньше. Теперь дерево можно уменьшить на один уровень с помощью тривиальной операции перестановки: правая ветвь «самого глубокого дерева-узла, но без поворота» теперь без левой ветки и без поворота становится левой ветвью узла дерева «самое глубокое дерево». узел кроме двух ".
• Теперь поиск наименьшего элемента можно снова продолжить «влево».

Древовидную структуру не нужно явно сохранять, поскольку она не содержит информации. Вместо этого в списке сохраняется последовательность чередующихся «листовых списков» и «сводных номеров». Поэтому мы и создали изначальный «список чисел».