clojure - 使用循环/递归的惰性序列？

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. (循环 [acc [] args args] ...) -> ((fn 步骤 [args] ...) args)
2. (if 条件 (recur ...) acc) -> (when 条件 (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))))