如果Clojure中唯一的非堆栈消耗循环结构是“recur”，那么这个lazy-seq是如何工作的呢？ [英] If the only non-stack-consuming looping construct in Clojure is "recur", how does this lazy-seq work?

问题描述

lazy-seq 的ClojureDocs页面提供了一个示例生成所有正数的延迟序列：

 （defn正数
 ]（正数1））
（[n]（cons n（lazy-seq（positive-numbers（inc n）））））
  

这个lazy-seq可以评估相当大的索引，而不会引发StackOverflowError（与同一页面上的筛选示例不同）：

  user => （nth（正数）99999999）
 100000000 
  

如果只有 recur 可以用来避免在递归函数中使用栈框架， -seq示例看起来可以调用自身而不会溢出堆栈？

解决方案

thunk。它不会立即调用。当请求每个元素（或者元素的块，视情况而定）时，调用下一个thunk来检索该值。该thunk可以创建另一个thunk来表示序列的尾部（如果它继续）。神奇的是（1）这些特殊的thunk实现序列接口并且可以透明地被使用，并且（2）每个thunk仅被调用一次 - 其值被缓存 - 因此实现的部分是值序列。 / p>

这里是一般的想法，没有魔法，只是良好的ol功能：

 （nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn ）））
 
（defn my-next [s]（（second s）））
 
（defn my-realize [sn] 
 []，ss，nn] 
（if（pos？n）
（recur（conj a（first s））（my-next s）（dec n））
a） 
 
 user => （ - >（my-thunk-seq）first）
 1 
 user => （ - >（my-thunk-seq）my-next first）
 2 
 user => （我的意识（my-thunk-seq）10）
 [1 2 3 4 5 6 7 8 9 10] 
 user => （count（my-realize（my-thunk-seq）100000））
 100000;级栈消耗
  

魔术位发生在 clojure.lang.LazySeq 在Java中定义，但我们实际上可以直接在Clojure中实现魔术（下面的例子中的实现），通过在类型上实现接口并使用原子来缓存。

 （deftype MyLazySeq [thunk-mem] 
 clojure.lang.Seqable 
（seq [_] 
 fn？@ thunk-mem）
（swap！thunk-mem（fn [f]（seq（f）））））
 @ thunk-mem）
;实现ISeq是必要的，因为
 clojure.lang.ISeq 
（首先[这个]（第一个（seq这个）））
下一页（下一页））
（更多[this]（rest（seq this）））
（cons [this x]（cons x（seq this））））
 
（defmacro my-lazy-seq [& body] 
`（MyLazySeq。（atom（fn []〜@ body）））
  

现在已经可以使用 take 等，但是以调用 lazy-seq 我们将使用 my-take

 （defn my-lazy-seq  [n coll] 
（my-lazy-seq 
（when（pos？ n）
（when-let [s（seq coll）] 
（cons（first s）（my-take（dec n）（rest s））））））
  

现在让我们使用一个缓慢的无限序列来测试缓存行为。

 （defn slow-inc [n]（Thread / sleep 1000）（inc n））
 
（defn slow-pos-nums 
 []（慢速度1））
（[n]（cons-lazy-seq（slow-pos-nums（slow-inc n）））））
  

和REPL测试

  user => （def nums（slow-pos-nums））
＃'user / nums 
 user => （时间（doall（my-take 10 nums）））
经过时间：9000.384616 msecs
（1 2 3 4 5 6 7 8 9 10）
 user => （时间（doall（my-take 10 nums）））
经过时间：0.043146 msecs
（1 2 3 4 5 6 7 8 9 10）
  




The ClojureDocs page for lazy-seq gives an example of generating a lazy-seq of all positive numbers:

(defn positive-numbers
  ([] (positive-numbers 1))
  ([n] (cons n (lazy-seq (positive-numbers (inc n))))))

This lazy-seq can be evaluated for pretty large indexes without throwing a StackOverflowError (unlike the sieve example on the same page):

user=> (nth (positive-numbers) 99999999)
100000000

If only recur can be used to avoid consuming stack frames in a recursive function, how is it possible this lazy-seq example can seemingly call itself without overflowing the stack?

解决方案

A lazy sequence has the rest of the sequence generating calculation in a thunk. It is not immediately called. As each element (or chunk of elements as the case may be) is requested, a call to the next thunk is made to retrieve the value(s). That thunk may create another thunk to represent the tail of the sequence if it continues. The magic is that (1) these special thunks implement the sequence interface and can transparently be used as such and (2) each thunk is only called once -- its value is cached -- so the realized portion is a sequence of values.

Here it is the general idea without the magic, just good ol' functions:

(defn my-thunk-seq 
  ([] (my-thunk-seq 1)) 
  ([n] (list n #(my-thunk-seq (inc n)))))

(defn my-next [s] ((second s)))

(defn my-realize [s n] 
  (loop [a [], s s, n n] 
    (if (pos? n) 
      (recur (conj a (first s)) (my-next s) (dec n)) 
      a)))

user=> (-> (my-thunk-seq) first)
1
user=> (-> (my-thunk-seq) my-next first)
2
user=> (my-realize (my-thunk-seq) 10)
[1 2 3 4 5 6 7 8 9 10]
user=> (count (my-realize (my-thunk-seq) 100000))
100000 ; Level stack consumption

The magic bits happen inside of clojure.lang.LazySeq defined in Java, but we can actually do the magic directly in Clojure (implementation that follows for example purposes), by implementing the interfaces on a type and using an atom to cache.

(deftype MyLazySeq [thunk-mem]
  clojure.lang.Seqable 
  (seq [_] 
    (if (fn? @thunk-mem) 
      (swap! thunk-mem (fn [f] (seq (f)))))
      @thunk-mem)
  ;Implementing ISeq is necessary because cons calls seq
  ;on anyone who does not, which would force realization.
  clojure.lang.ISeq
  (first [this] (first (seq this)))
  (next [this] (next (seq this)))
  (more [this] (rest (seq this)))
  (cons [this x] (cons x (seq this))))

(defmacro my-lazy-seq [& body] 
  `(MyLazySeq. (atom (fn [] ~@body))))

Now this already works with take, etc., but as take calls lazy-seq we'll make a my-take that uses my-lazy-seq instead to eliminate any confusion.

(defn my-take
  [n coll]
  (my-lazy-seq
   (when (pos? n)
     (when-let [s (seq coll)]
      (cons (first s) (my-take (dec n) (rest s)))))))

Now let's make a slow infinite sequence to test the caching behavior.

(defn slow-inc [n] (Thread/sleep 1000) (inc n))

(defn slow-pos-nums 
  ([] (slow-pos-nums 1)) 
  ([n] (cons n (my-lazy-seq (slow-pos-nums (slow-inc n))))))

And the REPL test

user=> (def nums (slow-pos-nums))
#'user/nums
user=> (time (doall (my-take 10 nums)))
"Elapsed time: 9000.384616 msecs"
(1 2 3 4 5 6 7 8 9 10)
user=> (time (doall (my-take 10 nums)))
"Elapsed time: 0.043146 msecs"
 (1 2 3 4 5 6 7 8 9 10)

这篇关于如果Clojure中唯一的非堆栈消耗循环结构是“recur”，那么这个lazy-seq是如何工作的呢？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！