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

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

1> WuHoUnited..：

---

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

---

懒惰与短路有关.在Clojure中,序列和宏可以是惰性的,但函数应用却不是.在Haskell中,函数应用程序本身是懒惰的(这与它们被咖喱的事实联系在一起).在Clojure中,定义一个函数`multiply`是不可能的,当`0`是左参数时,它不会评估右手参数,因为在Clojure中,参数在传递给函数之前得到了评估.这就是为什么像`if`,`和`,`或`,`if-not`等不是函数的原因.在Haskell中,所有这些都可以是常规函数.

---

在你的答案中提及新的`clojure.core/reduced`功能是否值得？

---

非常有趣的问答(两者都是+1).

---

尾递归真的与此相关吗？我不认为`foldr`是尾递归的; 如果是的话,这是一种奇怪的与thunk相关的尾递归,我还不了解,并且很想学习.

---

vemv,在你给出的例子中,它实际上是短路的`和`,导致'42'不被打印,而不是短路的减少.如果您尝试其他一些示例,您可以看到差异.例如`(reduce#(和%1%2)(cons false(repeat true)))`不会终止,但是懒惰语言中的等效右折叠将能够避免尝试评估整个序列.

2> James Vander..：

---

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

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

因此，如果您想对折，可以使用一些有效的替代方法

请改用向量。

使用延迟序列。

用于reduced短路reduce。

如果您真的想潜入兔子洞，请使用传感器。