我们如何做左和右折叠在Clojure? [英] How do we do both left and right folds in Clojure?
问题描述
减少工作正常,但它更像折叠左。
Reduce works fine but it is more like fold-left. Is there any other form of reduce that lets me fold to right ?
推荐答案
clojure标准库的原因是什么?只有fold-left(reduce)实际上是非常微妙的,这是因为clojure不够懒惰得到fold-right的主要好处。
The reason that the clojure standard library only has fold-left (reduce) is actually very subtle and it is because clojure isn't lazy enough to get the main benefit of fold-right.
主要好处在像haskell这样的语言中的fold-right是它实际上可能短路。
如果我们做 foldr(&&)True [False,True,True,True,True],它实际获得评估的方式是非常有启发性的。唯一需要评估的是函数
和带有1个参数的
(第一个 False
)。一旦它到达那里,它知道答案,不需要评估任何 True
。
The main benefit of fold-right in languages like haskell is that it can actually short-circuit.
If we do foldr (&&) True [False, True, True, True, True]
the way that it actually gets evaluated is very enlightening. The only thing it needs to evaluate is the function and
with 1 argument (the first False
). Once it gets there it knows the answer and does not need to evaluate ANY of the True
s.
仔细观察图片:
你会看到,虽然从概念上来说,fold-right开始和列表的结尾并向前移动,但实际上,它开始在列表。
you will see that although conceptually fold-right starts and the end of the list and moves towards the front, in actuality, it starts evaluating at the FRONT of the list.
这是一个例子,其中lazy / curried函数和尾递归可以提供clojure不能带来的好处。
This is an example of where lazy/curried functions and tail recursion can give benefits that clojure can't.
根据vemv的推荐,我想提一下Clojure在核心命名空间添加了一个新函数围绕这个限制Clojure不能有懒惰的右折。在核心命名空间中有一个名为 reduced
的函数,它允许你使Clojure的 reduce
lazier。它可以用来短路 reduce
,告诉它不要看看列表的其余部分。例如,如果你想把数字列表相乘,但是有理由怀疑这个列表偶尔会包含零,并且想要处理它作为一个特殊情况,当你遇到一个零的时候不看列表的其余部分,你可以写以下 multiply-all
函数(请注意使用 reduced
表示最终答案为 0
,无论列表的其余部分是什么)。
Based on a recommendation from vemv, I would like to mention that Clojure added a new function to the core namespace to get around this limitation that Clojure can't have the lazy right fold. There is a function called reduced
in the core namespace which allows you to make Clojure's reduce
lazier. It can be used to short-circuit reduce
by telling it not to look at the rest of the list. For instance, if you wanted to multiply lists of numbers but had reason to suspect that the list would occasionally contain zero and wanted to handle that as a special case by not looking at the remainder of the list once you encountered a zero, you could write the following multiply-all
function (note the use of reduced
to indicate that the final answer is 0
regardless of what the rest of the list is).
(defn multiply-all [coll]
(reduce
(fn [accumulator next-value]
(if (zero? next-value)
(reduced 0)
(* accumulator next-value)))
1
coll))
它短路,你可以乘以一个无限的数字列表,碰巧包含一个零,看到它确实以 0
And then to prove that it short-circuits you could multiply an infinite list of numbers which happens to contain a zero and see that it does indeed terminate with the answer of 0
(multiply-all
(cycle [1 2 3 4 0]))
这篇关于我们如何做左和右折叠在Clojure?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!