使用循环/重复的懒惰序列？

Question

我想为一个生成无限结果序列的算法编写一个实现,其中每个元素代表算法的单个迭代的计算.使用懒惰序列是方便的,因为它解耦迭代次数的逻辑(通过使用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更喜欢,因为:

• 更明显的是初始条件是什么以及算法如何进展到下一次迭代.
• 由于尾部优化,它不会受到堆栈溢出的影响.

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

附录

如果您正在寻找一种模式,用于将像您这样的热切循环转换为惰性循环

1. (loop [acc [] args args] ...) - > ((fn step [args] ...) args)
2. (if condition (recur ...) acc) - > (when condition (lazy-seq ...)
3. (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))))

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