懒惰和堆栈溢出

Question

我写了以下内容:

(fn r [f xs]
  (lazy-seq
    (if (empty? xs)
    '()
    (cons (f (first xs)) (r f (rest xs))))))

解决4clojure.com的问题#118:http://www.4clojure.com/problem/118

它要求重新实现地图而不使用地图等,并且该解决方案通过了测试(我不知道它是否正确:它与其他解决方案非常接近).

因为问题表明它必须是懒惰的,我通过在lazy-seq中 "包装"我的解决方案来编写上面的代码...但是我不明白lazy-seq是如何工作的.

我不明白这里什么是"懒惰",也不知道如何测试它.

当我问(type ...)我得到一个clojure.lang.LazySeq时,不出所料,但我不知道如果我只是删除了lazy-seq "wrap" ,那和我之间的区别是什么.

现在当然如果我删除了lazy-seq,我得到一个stackoverflow为什么要尝试执行这个:

(= [(int 1e6) (int (inc 1e6))]
   (->> (... inc (range))
        (drop (dec 1e6))
        (take 2)))

否则(即:如果我让lazy-seq包裹到位),它似乎工作正常.

所以我决定尝试以某种方式"调试"/追踪正在发生的事情,试图了解它是如何工作的.我采用了以下宏(我在SO IIRC上发现):

(defmacro dbg [x] `(let [x# ~x] (println "dbg: " '~x "=" x#) x#))

并将工作版本包装在dbg宏中并尝试再次执行它.而现在kaboom:现在运行良好的版本也会抛出堆栈溢出.

现在我不确定:也许这是宏的一个不受欢迎的影响,会以某种方式强制评估否则不会被评估的东西？

如果有人能够解释,使用这个简单的函数和简单的测试,懒惰在这里如何工作,什么时候被调用,等等将是很好的.

Answer 1

整个魔力在于clojure.lang.LazySeq java 类。它本身实现了 ISeq 接口，并且宏的 s-表达式参数lazy-seq被转换为不带任何参数的函数，并传递给 clojure.lang.LazySeq 的构造函数（传递给以IFn对象作为参数的构造函数），因为最后您再次调用了r函数（返回一个列表ISeq而不是完整列表），这允许 LazySeq 延迟评估项目。

所以基本上流程是这样的：

• LazySeq 调用传递给它的 Fn（即代码的其余部分）
• 此 Fn 调用返回一个 ISeq，因为 Lists 实现了 ISeq。由于递归调用，这将返回 ISeq（列表），其中第一个值作为具体值，第二个值是 LazySeq 对象r。返回的 ISeq 存储在类中的局部变量中。
• LazySeq 的 ISeq 实现在调用下一项时会调用上面步骤中存储在本地类变量中的 ISeq（列表）的下一个，并检查它是否是 LazySeq 类型（由于调用，它将位于第二项中r），如果它是 LazySeq，然后对其进行评估并返回 item，否则直接返回该 item（您传递给 cons 的第一个具体值）

我知道这有点令人费解:)。r我刚才也浏览了 Java 代码，在我意识到神奇是可能的，因为对自身的递归调用返回一个惰性序列后，我才明白了这一点。现在你已经有了它，一种自定义分隔的延续:)