我想编写一个生成无限结果序列的算法的实现,其中每个元素代表算法单次迭代的计算。使用惰性序列很方便,因为它将迭代次数(通过使用 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)将加法从循环中取出,这样您就不必在如此多的序列上重复,并且(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)))
附录
如果您正在寻找一种模式来将像您这样的急切循环转换为惰性序列
(循环 [acc [] args args] ...)
->((fn 步骤 [args] ...) args)
(if 条件 (recur ...) acc)
->(when 条件 (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))))
关于clojure - 使用循环/递归的惰性序列?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21712145/