在Clojure中使用递归生成lazy seq？

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.

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都返回懒惰序列.