clojure - 懒惰和堆栈溢出

我写了以下内容:

(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

它要求不使用map等来重新实现map，并且该解决方案通过了测试(我不知道它是否正确:它与所说的其他解决方案非常接近)。

因为问题表明它必须是惰性的，所以我通过在惰性序列中“包装”我的解决方案来编写了上面的代码。但是，我不明白惰性序列是如何工作的。

我不明白什么是“懒惰”，也不知道如何测试。

毫无疑问，当我问(type ...)时，我得到一个clojure.lang.LazySeq，但是我不知道这和我简单地删除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:运行良好的版本现在也引发了stackoverflow。

现在我不确定:也许这是宏的有害影响，它将以某种方式迫使评估某些东西，否则这些东西将无法被评估？

如果有人可以使用此简单的功能和简单的测试来解释懒惰在这里的工作方式，何时确切调用什么等等，那将是很好的。

最佳答案

整个魔术在于clojure.lang.LazySeq java类。本身实现ISeq接口(interface)和lazy-seq宏的s-expressions参数被转换为不带任何参数的函数，并传递给clojure.lang.LazySeq的构造函数(传递给以IFn对象作为参数的构造函数)，并且因为最后，您再次调用了r函数(返回的是ISeq而不是完整列表)，这使LazySeq可以懒惰地评估项目。

因此，基本上，流程如下所示:

LazySeq调用传递给它的Fn(即代码的其余部分)

因为Lists实现ISeq，所以此Fn调用返回一个ISeq。由于对r的递归调用，此返回的ISeq(列表)的第一个值是具体值，第二个是LazySeq对象。返回的ISeq存储在类的局部变量中。

调用下一个项目时，LazySeq的ISeq实现会调用在上一步中存储在本地类变量中的下一个ISeq(列表)，并检查其是否为LazySeq类型(由于r调用，它将位于第二个项目中) ，如果它是LazySeq，则求值并返回，然后返回item，否则直接返回item(传递给cons的第一个具体值)

我知道这是一件令人费解的事情:)。我现在还浏览了Java代码，在意识到魔术是可能的之后就能够弄清楚了，因为对r的递归调用本身返回了一个惰性序列。这样就可以了，这是自定义分隔的延续:)