我们如何在Clojure中进行左右折叠？

Question

减少工作正常,但它更像折叠左.有没有其他形式的减少让我折叠到右边？

Answer 1

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

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

如果仔细观察图片:

你会看到虽然概念上右折开始和列表的结尾向前移动,但实际上,它开始在列表的前面进行评估.

这是一个例子,其中惰性/ curried函数和尾递归可以提供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]))

Answer 2

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

(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))))

注意，只有foldl在尾部位置，并且递归调用可以替换为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. 如果您真的想潜入兔子洞，请使用传感器。