mapcat打破了懒惰

Question

我有一个函数生成称为函数的惰性序列.

如果我运行代码:

(map a-function a-sequence-of-values) 

它按预期返回一个惰性序列.

但是当我运行代码时:

(mapcat a-function a-sequence-of-values) 

它打破了我的功能的懒惰.事实上,它将代码转换为

(apply concat (map a-function a-sequence-of-values)) 

因此,在连接这些值之前,需要从地图中实现所有值.

我需要的是一个函数,它可以根据需要连接map函数的结果,而不事先预先知道所有的map.

我可以为此修改一个函数:

(defn my-mapcat
  [f coll]
  (lazy-seq
   (if (not-empty coll)
     (concat
      (f (first coll))
      (my-mapcat f (rest coll))))))

但我不敢相信clojure没有做过任何事情.你知道clojure有这样的功能吗？只有少数人和我有同样的问题？

我还找到了一个处理相同问题的博客:http://clojurian.blogspot.com.br/2012/11/beware-of-mapcat.html

Answer 1

懒惰序列的生产和消费与懒惰评估不同.

Clojure函数对其参数进行严格/急切的评估.对产生惰性序列的论证的评估不会强制实现所产生的惰性序列本身.但是,会发生由参数评估引起的任何副作用.

通常的用例mapcat是连接没有副作用的序列.因此,急切评估某些论点并不重要,因为预计不会产生副作用.

你的函数my-mapcat通过将它们包装在thunk(其他lazy-seqs)中来对其参数的评估施加额外的懒惰.当需要显着的副作用 - IO,显着的内存消耗,状态更新时,这可能很有用.但是,如果你的函数正在产生副作用并产生一个连续的序列,你的代码可能需要重构,警告铃声可能会在你的头脑中消失.

这与algo.monads类似

(defn- flatten*
  "Like #(apply concat %), but fully lazy: it evaluates each sublist
   only when it is needed."
  [ss]
  (lazy-seq
    (when-let [s (seq ss)]
      (concat (first s) (flatten* (rest s))))))

另一种写作方式my-mapcat:

(defn my-mapcat [f coll] (for [x coll, fx (f x)] fx))

将函数应用于惰性序列将强制实现满足函数的自变量所必需的一部分延迟序列.如果该函数本身产生惰性序列,那么这些当然不是实现的.

考虑此函数来计算序列的已实现部分

(defn count-realized [s] 
  (loop [s s, n 0] 
    (if (instance? clojure.lang.IPending s)
      (if (and (realized? s) (seq s))
        (recur (rest s) (inc n))
        n)
      (if (seq s)
        (recur (rest s) (inc n))
        n))))

现在让我们看看正在实现的目标

(let [seq-of-seqs (map range (list 1 2 3 4 5 6))
      concat-seq (apply concat seq-of-seqs)]
  (println "seq-of-seqs: " (count-realized seq-of-seqs))
  (println "concat-seq: " (count-realized concat-seq))
  (println "seqs-in-seq: " (mapv count-realized seq-of-seqs)))          

 ;=> seq-of-seqs:  4
 ;   concat-seq:  0
 ;   seqs-in-seq:  [0 0 0 0 0 0]

因此,seq-of-seqs的4个元素已经实现,但是没有实现其组件序列,也没有在连接序列中实现任何实现.

为什么4？因为适用的arity重载版本concat需要4个参数[x y & xs](计数&).

相比于

(let [seq-of-seqs (map range (list 1 2 3 4 5 6))
      foo-seq (apply (fn foo [& more] more) seq-of-seqs)]
  (println "seq-of-seqs: " (count-realized seq-of-seqs))
  (println "seqs-in-seq: " (mapv count-realized seq-of-seqs)))

;=> seq-of-seqs:  2
;   seqs-in-seq:  [0 0 0 0 0 0]

(let [seq-of-seqs (map range (list 1 2 3 4 5 6))
      foo-seq (apply (fn foo [a b c & more] more) seq-of-seqs)]
  (println "seq-of-seqs: " (count-realized seq-of-seqs))
  (println "seqs-in-seq: " (mapv count-realized seq-of-seqs)))

;=> seq-of-seqs:  5
;   seqs-in-seq:  [0 0 0 0 0 0]

Clojure有两个解决方案来评估懒惰的论点.

一个是宏.与函数不同,宏不会评估它们的参数.

这是一个带副作用的功能

(defn f [n] (println "foo!") (repeat n n))

即使没有实现序列,也会产生副作用

user=> (def x (concat (f 1) (f 2)))
foo!
foo!
#'user/x
user=> (count-realized x)
0

Clojure有一个lazy-cat宏来防止这种情况发生

user=> (def y (lazy-cat (f 1) (f 2)))
#'user/y
user=> (count-realized y)
0
user=> (dorun y)
foo!
foo!
nil
user=> (count-realized y)
3
user=> y
(1 2 2)

不幸的是,你不能apply一个宏.

延迟评估的另一个解决方案是用thunk进行包装,这正是你所做的.

Answer 2

你的前提是错的.Concat是懒惰的,如果它的第一个参数是,则apply是懒惰的,而mapcat是懒惰的.

user> (class (mapcat (fn [x y] (println x y) (list x y)) (range) (range)))
0 0
1 1
2 2
3 3
clojure.lang.LazySeq

请注意,一些初始值被评估(更多内容在下面),但显然整个事情仍然是懒惰的(或者调用永远不会返回,(range)返回无限序列,并且在急切使用时不会返回).

你链接到的博客是关于在懒惰的树上递归使用mapcat的危险,因为它渴望前几个元素(可以在递归应用程序中加起来).