如何理解clojure的懒惰seq

Question

我试图理解clojure的lazy-seq运算符,以及懒惰评估的概念.我知道这个概念背后的基本思想:表达式的评估会延迟到需要的值.

一般来说,这可以通过两种方式实现:

• 在编译时使用宏或特殊形式;
• 在运行时使用lambda函数

使用惰性求值技术,可以构造被评估为已消耗的无限数据结构.这些无限序列利用lambdas,闭包和递归.在clojure中,这些无限数据结构是使用lazy-seq和cons形成的.

我想知道lazy-seq它是如何神奇的.我知道它实际上是一个宏.请考虑以下示例.

(defn rep [n]
  (lazy-seq (cons n (rep n))))

这里,rep函数返回一个延迟评估的类型序列LazySeq,现在可以使用序列API对其进行转换和使用(从而进行求值).这个API提供的功能take,map,filter和reduce.

在扩展形式中,我们可以看到lambda如何用于存储单元格的配方而不立即进行评估.

(defn rep [n]
  (new clojure.lang.LazySeq (fn* [] (cons n (rep n))))) 

• 但序列API实际上如何使用LazySeq？
• 以下表达式实际发生了什么？

(reduce + (take 3 (map inc (rep 5))))

• 如何将中间操作map应用于序列,
• 如何take限制序列和
• 终端操作如何reduce评估序列？

另外,这些功能如何与a Vector或a一起使用LazySeq？

此外,是否可以生成嵌套的无限数据结构？:包含列表的列表,包含列表,包含列表......无限宽和深,评估为序列API消耗？

最后一个问题,这是否存在实际差异

(defn rep [n]
  (lazy-seq (cons n (rep n))))

这个？

(defn rep [n]
  (cons n (lazy-seq (rep n))))

Answer 1

这是很多问题!

seq API如何与LazySeq实际配合使用？

如果你看一下LazySeq类的源代码,你会发现它实现了ISeq接口提供方法,比如first,more和next.

喜欢的功能map,take并filter内置使用lazy-seq(他们生产的懒惰序列)和first和rest(又使用more),这就是他们如何与懒以次作为其输入采集工作-通过使用first和more的实现LazySeq类.

以下表达式实际发生了什么？

(reduce + (take 3 (map inc (rep 5))))

关键是要看看它是如何LazySeq.first运作的.它将调用包装函数来获取和记忆结果.在您的情况下,它将是以下代码:

(cons n (rep n))

因此,它将是一个cons单元,n其值和另一个LazySeq实例(递归调用的结果rep)作为其rest一部分.它将成为此LazySeq对象的实现值,first并将返回缓存的cons单元格的值.

当你调用more它时,它将以相同的方式确保LazySeq实现特定对象的值(或重用的memoized值)并调用more它(在这种情况下more,在包含另一个LazySeq对象的cons单元格上).

一旦你获得另一个LazySeq对象实例,more当你调用first它时故事会重复.

map并且take将创造另一个lazy-seq,将调用first并more作为其参数(只是一个懒惰SEQ)越过集合所以这将是类似的故事.区别将是只在如何传递的值cons生成(如呼叫f通过获得的值first调用上LazySeq的映射,以价值map来代替原始值就像n在你的rep函数).

有了reduce它有点简单,因为它会使用loop与first和more在输入序列懒迭代和应用还原作用,产生最终结果.

由于实际的实现看起来像map,take我鼓励您检查他们的源代码 - 它很容易遵循.

seq API如何适用于不同的集合类型(例如lazy seq和persistent vector)？

如上所述,map,take等功能在以下方面的工作first和rest( -提醒rest上的顶部被实现more).因此,我们需要解释如何first和rest/或more可以使用不同的集合类型:它们检查集合是否实现ISeq(然后直接实现这些函数),或者它们尝试创建seq集合的视图并将其实现first与more.

是否可以生成嵌套的无限数据结构？

这绝对是可能的,但我不确定您希望得到的确切数据形状.你的意思是得到一个懒的seq,它生成另一个序列作为它的值(而不是像n你的单个值rep)但是将它作为一个平坦的序列返回？

(defn nested-cons [n]
  (lazy-seq (cons (repeat n n) (nested-cons (inc n)))))

(take 3 (nested-cons 1))

;; => ((1) (2 2) (3 3 3))

宁可回来(1 2 2 3 3 3)？

对于这种情况,您可以使用concat而不是cons创建两个或更多序列的延迟序列:

(defn nested-concat [n]
  (lazy-seq (concat (repeat n n) (nested-concat (inc n)))))

(take 6 (nested-concat 1))

;; => (1 2 2 3 3 3)

这有什么实际的区别吗？

(defn rep [n]
  (lazy-seq (cons n (rep n))))

还有这个？

(defn rep [n]
  (cons n (lazy-seq (rep n))))

在这个特殊情况下并不是真的.但是在cons单元格没有包装原始值而是函数调用的结果来计算它的情况下,后一种形式不是完全懒惰的.例如:

(defn calculate-sth [n]
  (println "Calculating" n)
  n)

(defn rep1 [n]
  (lazy-seq (cons (calculate-sth n) (rep1 (inc n)))))

(defn rep2 [n]
  (cons (calculate-sth n) (lazy-seq (rep2 (inc n)))))

(take 0 (rep1 1))
;; => ()

(take 0 (rep2 1))
;; Prints: Calculating 1
;; => ()

因此,后一种形式将评估其第一个元素,即使您可能不需要它.