在Clojure中使用递归生成惰性序列？

Question

我是新手学习Clojure，目前在学习“loop / recur”方面遇到了一些困难。我的问题基本上是为什么我的“自定义”range函数不能返回一个惰性序列。这个实现有什么问题或者在这种情况下不应该使用递归吗？

(defn my-range
  [nr]
  (loop [l nr acc '()]
    (if (< l 1)
      acc
      (recur (dec l) (conj acc l)))))

当我运行它时：

> (time (take 10 (my-range 100000))) ;; "Elapsed time: 85.443 msecs"
> (time (take 10 (range 100000))) ;; "Elapsed time: 0.095 msecs"

非常大的时间差让我相信列表首先被构建，然后再取10个。

- skamsie

---

标准的 range 从 0 开始，而不是 1。这不会影响问题。 - Thumbnail

Answer 1

在my-range中，您没有使用任何惰性结构。由于您是从末尾开始组装列表并朝向开头工作，因此访问前十个元素的唯一方法是先实现所有其他元素。

惰性序列从开头开始工作，像这样：

(defn my-range
  ([end]
   (my-range 1 end))
  ([start end]
   (when (<= start end)
     (lazy-seq (cons start (my-range (inc' start) end))))))

这里的技巧在于不返回已经实现的序列。相反，你返回一个存储该函数的对象：

#(cons start (my-range (inc' start) end))

当某人在该对象上调用seq时，它将调用上述函数，缓存其结果并返回该结果。对seq的未来调用将仅返回缓存的结果。请注意，您传递给cons的第二个参数也是一个惰性序列（因为对my-range的调用返回一个lazy-seq），因此只有在必要时才会被实现。

为了完整起见，另一种编写此函数的方法如下：

(defn my-range
  [end]
  (take end (iterate inc' 1)))

这是因为iterate和take都返回惰性序列。

- Sam Estep

---

非常感谢。我的Clojure知识非常有限，但我明白了你的意思。然而，我不明白为什么你使用inc'而不是inc？ - skamsie

请尝试执行 (inc Long/MAX_VALUE) 和 (inc' Long/MAX_VALUE)。 - Sam Estep