Clojure中的无限递归惰性序列在出现时会被视为空序列。

Question

Clojure中的无限递归惰性序列在出现时会被视为空序列。

3

假设我写了：

(def stuff
  (lazy-seq stuff))

当我在 REPL 中询问 stuff 的值时，我预期会被陷入无限循环，因为我定义了 stuff 为它自己（这几乎没有说明这个序列的任何信息）。

然而，我得到了一个空序列。

> stuff
()

为什么会这样呢？

编辑：我指的是递归数据，而不是递归函数。

我仍然对为什么序列终止感到困惑。相比之下，以下代码陷入了无限循环（并且导致堆栈溢出）。

(def stuff
  (lazy-seq (cons (first stuff) [])))

一些背景：这个问题来自于我尝试使用埃拉托色尼筛法实现素数生成器。我的第一次尝试是：

(def primes
  (lazy-seq (cons 2
                  (remove (fn [x]
                            (let [ps (take-while #(< % x) primes)]
                              (some #(zero? (mod x %)) ps)))
                          (range 3 inf))))) ;; My customized range function that returns an infinite sequence

我原本以为这样做行不通，因为 take-while 即使无法计算出更多的质数仍然会继续请求。但让我惊讶的是它的效果还不错。

> (take 20 primes)
(2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71)

- Yizhe Sun

它无法产生无限循环，因为那里没有函数调用。而会产生预期的无限循环的是(defn stuff [] (lazy-seq (stuff)))。 - leetwinski

@leetwinski 只使用惰性序列就可以产生无限循环。请查看我的编辑。 - Yizhe Sun

take-while is limited by x, and x is a current primes 'cap', so it will never ask for more primes over the ones that are already generated. Also range already produces infinite seq, no need to customize it. (drop 3 (range)), or (iterate inc 3) - leetwinski

@leetwinski 它有效，但是为什么？比如我们需要检查5是否为质数。难道 some 不会遍历所有质数（包括5本身），并检查它们中是否有任何一个是因子吗？ - Yizhe Sun

1

@YizheSun，我研究了一下@leetwinski对primes的定义为什么有效，并在博客文章中写了一些内容：https://phillippe.siclait.com/blog/primes-lazy-sequence - Phillippe Siclait

显示剩余3条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Phillippe Siclait · Accepted Answer

首先，每个懒惰序列只能被实现一次。其次，你对stuff的定义没有使用递归--stuff不是一个函数。如果你看一下lazy-seq的定义，你就可以看到你对stuff的定义展开为：

(def stuff (new clojure.lang.LazySeq (fn* [] stuff)))

当调用clojure.lang.LazySeq构造函数的fn参数时，它返回已经被实现的相同的lazy seq。因此，当您尝试将懒seq打印到REPL时，迭代会立即终止并返回nil。

您可以验证stuff的类型为clojure.lang.LazySeq。

user=> (type stuff)
clojure.lang.LazySeq

在将stuff打印到REPL后，stuff已被实现。

user=> (realized? stuff)
false
user=> stuff
()
user=> (realized? stuff)
true

你可以使用递归来达到你期望的效果。

user=> (defn stuff
         []
         (lazy-seq (stuff)))
#'user/stuff
user=> (stuff) ;; Hangs forever.