47

减少工作正常，但它更像是向左折叠。有没有其他形式的 reduce 可以让我向右折叠？

4

2 回答 2

91

clojure 标准库只有 fold-left (reduce) 的原因实际上非常微妙，这是因为 clojure 不够懒惰，无法获得 fold-right 的主要好处。

像 haskell 这样的语言中 fold-right 的主要好处是它实际上可以短路。如果我们按照foldr (&&) True [False, True, True, True, True]实际进行评估的方式进行，那将是非常有启发性的。它唯一需要评估的是and带有 1 个参数的函数（第一个False）。一旦它到达那里，它就知道答案并且不需要评估任何Trues。

如果你仔细看图片：

在此处输入图像描述

您会看到，尽管从概念上讲，右折叠从列表的末尾开始并移到前面，但实际上，它从列表的前面开始评估。

这是一个例子，说明惰性/柯里化函数和尾递归可以带来 clojure 无法提供的好处。

奖金部分（有兴趣的人）

根据 vemv 的建议，我想提一下 Clojure 向核心命名空间添加了一个新函数，以解决 Clojure 不能具有惰性右折叠的限制。在核心命名空间中调用了一个函数reduced，它允许您使 Clojure 更reduce懒惰。reduce它可以通过告诉它不要查看列表的其余部分来用于短路。例如，如果您想将数字列表相乘，但有理由怀疑该列表偶尔会包含零，并且希望通过在遇到零时不查看列表的其余部分来处理这种情况，您可以编写以下multiply-all函数（注意使用reduced表示最终答案0与列表的其余部分无关）。

(defn multiply-all [coll]
  (reduce
   (fn [accumulator next-value]
     (if (zero? next-value)
       (reduced 0)
       (* accumulator next-value)))
   1
   coll))

然后为了证明它短路，您可以乘以一个恰好包含零的无限数字列表，并看到它确实以以下答案终止0

(multiply-all
 (cycle [1 2 3 4 0]))
于 2013-05-28T13:39:10.960 回答
11

让我们看一下每个可能的定义：

(defn foldl [f val coll]
  (if (empty? coll) val
    (foldl f (f val (first coll)) (rest coll))))

(defn foldr [f val coll]
  (if (empty? coll) val
    (f (foldr f val (rest coll)) (first coll))))

注意 onlyfoldl在尾部位置，递归调用可以替换为recur. 所以用recur,foldl不会占用堆栈空间，而foldr会。这就是为什么reduce喜欢foldl。现在让我们尝试一下：

(foldl + 0 [1 2 3]) ;6
(foldl - 0 [1 2 3]) ;-6
(foldl conj  [] [1 2 3]) ;[1 2 3]
(foldl conj '() [1 2 3]) ;(3 2 1)

(foldr + 0 [1 2 3]) ;6
(foldr - 0 [1 2 3]) ;-6
(foldr conj  [] [1 2 3]) ;[3 2 1]
(foldr conj '() [1 2 3]) ;(1 2 3)

你有什么理由想要弃牌吗？我认为最常见的用法foldr是将列表从前到后放在一起。在 Clojure 中我们不需要它，因为我们可以只使用向量来代替。避免堆栈溢出的另一个选择是使用惰性序列：

(defn make-list [coll]
  (lazy-seq
    (cons (first coll) (rest coll))))

所以，如果你想正确弃牌，一些有效的选择是

  1. 请改用向量。
  2. 使用惰性序列。
  3. 用于reduced短路reduce。
  4. 如果您真的想潜入兔子洞，请使用换能器。
于 2017-01-21T02:02:44.530 回答