Ленивая последовательность с использованием loop/recur?

Я хотел бы написать реализацию алгоритму, который создает бесконечную последовательность результатов, где каждый элемент представляет собой вычисление одной итерации алгоритма. Использование ленивой последовательности удобно, поскольку она отделяет логику количества итераций (с помощью take) и итераций сжигания (с помощью drop) из реализации.

Здесь приведен пример двух реализаций алгоритмов, один из которых создает ленивую последовательность (yadda-lazy), а другой - нет (yadda-loop).

(defn yadda-iter
  [v1 v2 v3]

  (+ (first v1)
     (first v2)
     (first v3)))

(defn yadda-lazy
  [len]

  (letfn [(inner [v1 v2 v3]
            (cons (yadda-iter v1 v2 v3)
                  (lazy-seq (inner (rest v1)
                                   (rest v2)
                                   (rest v3)))))]
    (let [base (cycle (range len))]
      (inner base
             (map #(* %1 %1) base)
             (map #(* %1 %1 %1) base)))))

(defn yadda-loop
  [len iters]

  (let [base (cycle (range len))]
    (loop [result nil
           i 0
           v1 base
           v2 (map #(* %1 %1) base)
           v3 (map #(* %1 %1 %1) base)]
      (if (= i iters)
        result
        (recur (cons (yadda-iter v1 v2 v3) result)
               (inc i)
               (rest v1)
               (rest v2)
               (rest v3))))))

(prn (take 11 (yadda-lazy 4)))
(prn (yadda-loop 4 11))

Есть ли способ создать ленивую последовательность, используя тот же стиль, что и loop/recur? Мне нравится yadda-loop лучше, потому что:

Это более очевидно, каковы начальные условия и как алгоритм переходит к следующей итерации.
Из-за оптимизации хвоста он не будет страдать от.

Ответ 1

Ваша версия цикла будет лучше написана для (1) вытащить добавление из цикла, чтобы вам не приходилось повторять так много последовательностей и (2) использовать conj на векторном аккумуляторе, чтобы ваши результаты были в том же порядке, что и ваш yadda-lazy.

(defn yadda-loop-2 [len iters]
  (let [v1 (cycle (range len))
        v2 (map * v1 v1)
        v3 (map * v1 v2)
         s (map + v1 v2 v3)]
    (loop [result [], s s, i 0]
      (if (= i iters)
        result
        (recur (conj result (first s)), (rest s), (inc i))))))

Однако в этот момент становится ясно, что цикл бесполезен, поскольку это просто

(defn yadda-loop-3 [len iters]
   (let [v1 (cycle (range len))
         v2 (map * v1 v1)
         v3 (map * v1 v2)
         s (map + v1 v2 v3)]
     (into [] (take iters s))))

и мы могли бы также вытащить параметр iters, вернуть просто s и take с него.

(defn yadda-yadda [len]
   (let [v1 (cycle (range len))
         v2 (map * v1 v1)
         v3 (map * v1 v2)]
     (map + v1 v2 v3)))

Это дает те же результаты, что и ваш yadda-lazy, также ленив и довольно ясен

(take 11 (yadda-yadda 4)) ;=> (0 3 14 39 0 3 14 39 0 3 14)

Вы также могли бы, эквивалентно

(defn yadda-yadda [len] 
  (as-> (range len) s 
        (cycle s)
        (take 3 (iterate (partial map * s) s))
        (apply map + s)))

добавление

Если вы ищете шаблон для преобразования нетерпеливого цикла, подобного вашему, в ленивую последовательность

(loop [acc [] args args]...) → ((fn step [args]...) args)
(if condition (recur...) acc) → (when condition (lazy-seq...)
(recur (conj acc (f...))...) → (lazy-seq (cons (f...) (step...)))

Применяя это к вашему yadda-lazy

(defn yadda-lazy-2 [len iters]
  (let [base (cycle (range len))]
    ((fn step [i, v1, v2, v3]
      (when (< i iters)
        (lazy-seq 
          (cons (yadda-iter v1 v2 v3)
            (step (inc i), (rest v1), (rest v2), (rest v3))))))
      0, base, (map #(* %1 %1) base), (map #(* %1 %1 %1) base))))

И в этот момент вы, вероятно, хотите, чтобы вытащить iters

(defn yadda-lazy-3 [len]
  (let [base (cycle (range len))]
    ((fn step [v1, v2, v3]
        (lazy-seq 
          (cons (yadda-iter v1 v2 v3)
            (step (rest v1), (rest v2), (rest v3)))))
      base, (map #(* %1 %1) base), (map #(* %1 %1 %1) base))))

Так что вы можете

(take 11 (yadda-lazy-3 4)) ;=> (0 3 14 39 0 3 14 39 0 3 14)

И тогда вы могли бы сказать: эй, мой yadda-iter просто применяет + на первом, а step применяется к остальным, так почему бы не объединить мои v1, v2, v3 и сделать это немного яснее?

(defn yadda-lazy-4 [len]
  (let [base (cycle (range len))]
    ((fn step [vs]
        (lazy-seq 
          (cons (apply + (map first vs))
            (step (map rest vs)))))
      [base, (map #(* %1 %1) base), (map #(* %1 %1 %1) base)])))

И вот, вы только что переделали вариационную карту

(defn yadda-lazy-5 [len]
  (let [base (cycle (range len))]
    (map + base, (map #(* %1 %1) base), (map #(* %1 %1 %1) base))))

Ответ 2

@Ответ A.Webb - это прекрасно, но если ваша любовь к loop/recur преодолеет его аргументы, знайте, что вы все равно можете объединить оба стиля рекурсии.

Например, взгляните на реализацию range:

(defn range
  (...)
  ([start end step]
   (lazy-seq
    (let [b (chunk-buffer 32)
          comp (cond (or (zero? step) (= start end)) not=
                     (pos? step) <
                     (neg? step) >)]
      (loop [i start]                        ;; chunk building through loop/recur
        (if (and (< (count b) 32)
                 (comp i end))
          (do
            (chunk-append b i)
            (recur (+ i step)))
          (chunk-cons (chunk b) 
                      (when (comp i end) 
                        (range i end step))))))))) ;; lazy recursive call

Вот еще один пример, альтернативная реализация filter:

(defn filter [pred coll]
  (letfn [(step [pred coll]
            (when-let [[x & more] (seq coll)]
              (if (pred x)
                (cons x (lazy-seq (step pred more))) ;; lazy recursive call
                (recur pred more))))]                ;; eager recursive call
    (lazy-seq (step pred coll))))

Ответ 3

Библиотека Tupelo имеет новую функцию lazy-gen/yield которая имитирует generator functions в Python. Он может генерировать ленивую последовательность из любой точки в структуре цикла. Вот версия yadda-loop которая показывает lazy-gen & yield в действии:

(ns tst.xyz
  (:use clojure.test tupelo.test)
  (:require [tupelo.core :as t] ))

(defn yadda-lazy-gen
  [len iters]
  (t/lazy-gen
    (let [base (cycle (range len))]
      (loop [i      0
             v1     base
             v2     (map #(* %1 %1) base)
             v3     (map #(* %1 %1 %1) base)]
        (when (< i iters)
          (t/yield (yadda-iter v1 v2 v3))
          (recur
            (inc i)
            (rest v1)
            (rest v2)
            (rest v3)))))))

Testing tst.clj.core
(take 11 (yadda-lazy 4))  => (0 3 14 39 0 3 14 39 0 3 14)
(yadda-loop 4 11)         => (0 3 14 39 0 3 14 39 0 3 14)
(yadda-lazy-gen 4 11)     => (0 3 14 39 0 3 14 39 0 3 14)

Ran 1 tests containing 1 assertions.
0 failures, 0 errors.