Clojure 中最简单的惰性函数

Question

我很难理解懒惰。

有人可以帮助我理解为什么下面的函数不是惰性函数，

(defn my-red
    ([f coll] (my-red f (first coll) (rest coll) ))
    ([f init coll] 
      (let [mr (fn [g i c d] 
            (if (empty? c) d 
        (recur  g (g  i (first c)) (rest c)  (conj d (g  i (first c)) ))))] 
    (lazy-seq (mr f init coll [])))))

而 clojure.org/lazy 上给出的示例是

(defn filter
  "Returns a lazy sequence of the items in coll for which
  (pred item) returns true. pred must be free of side-effects."
  [pred coll]
  (let [step (fn [p c]
                 (when-let [s (seq c)]
                   (if (p (first s))
                     (cons (first s) (filter p (rest s)))
                     (recur p (rest s)))))]
    (lazy-seq (step pred coll))))

Answer 1

filter 中的惰性来自于递归循环的 if 分支中对 filter 的调用。这就是代码遇到另一个lazy-seq并停止评估seq直到请求另一个元素的地方。

您的 my-red 实现一次且仅一次调用了 lazy-seq，这意味着您的 seq 要么根本不评估，要么完全评估。

Answer 2

mr 函数将在整个 coll 中重复出现。也许你的缩进误导了你。正确缩进，并删除了一些无用的参数，该函数看起来像这样：

(defn my-red
  ([f coll] (my-red f (first coll) (rest coll) ))
  ([f init coll] 
     (let [mr (fn [i c d] 
                (if (empty? c)
                  d 
                  (recur (f i (first c))
                         (rest c)
                         (conj d (f i (first c))))))] 
       (lazy-seq (mr init coll [])))))

基本上，您正在围绕 mr 函数进行包装（惰性序列），该函数在一个大的递归循环中完成所有工作。

Answer 3

lazy-seq 所做的只是获取其参数并延迟执行。为了产生真正的惰性序列，每个链接都必须包装在惰性序列调用中。惰性的“粒度”是在调用lazy-seq之间完成了多少工作。解决这个问题的一种方法是使用返回惰性序列的高级函数。

此外，尾递归和惰性是相互排斥的。这不会导致堆栈溢出，因为在每一步中，递归调用都会被包装到惰性 seq 中并返回。如果调用者随后尝试计算惰性 seq，则会调用递归调用，但它是由序列函数的原始调用者调用的，而不是序列函数本身，这意味着堆栈不会增长。这有点类似于通过 Trampoline 实现优化尾递归的想法（参见 Clojure 的 Trampoline 函数）。

这是一个惰性版本：

(defn my-red
  ([f coll] (my-red f (first coll) (rest coll) ))
  ([f init coll] 
   (let [mr (fn mr [g i c] 
              (if (empty? c)
                nil
                (let [gi (g  i (first c))]
                  (lazy-seq (cons gi (mr g gi (rest c)))))))] 
     (lazy-seq (mr f init coll)))))

请注意每次运行 mr 如何立即返回 nil 或惰性 seq，并且递归调用来自于 lazy-seq 调用。