haskell 中的 foldr 函数在这种情况下如何工作？

Question

所以我是 haskell 的新手，我遇到了以下表达式，我不太明白它是如何工作的： foldr (.) (+3) [(*2), (+5)] 13 它给出了结果：42 现在我知道 foldr 通常在这样的例子中工作： foldr (+) 0 [1,2,3] 比如： (1+(2+(0+3))) 但是添加另一个函数 (.) 我有点困惑。所以，如果你们中的任何人能准确地向我解释 haskell 是如何解释这个表达式的，那就太好了，谢谢！

Answer 1

评论可能已经为您解决了这个问题。但是，如果不是：

(.)是函数组成：

f . g
= \x -> f $ g $ x
= \x -> f (g x).

像 (* 2) 这样的形式是 \x -> x * 2

形式函数的糖分

现在，观察一下

foldr op base [a,b]

与

相同

a `op` (b `op` base)

当然，这也适用于更多参数。例如，

foldr (+) 0 [1,2,3,4,5]

只是

1 + 2 + 3 + 4 + 5 + 0

在你的情况下，你问的是

foldr (.) (+3) [(*2), (+5)]

这是（对于 Integer）

(*2) . (+5) . (+3)
= \x -> (*2) $ (+5) $ (+3) $ x
= \x -> (*2) $ (+5) $ x + 3
= \x -> (*2) $ x + 3 + 5
= \x -> (x + 3 + 5) * 2
= \x -> x*2 + 16

等等

foldr (.) (+3) [(*2), (+5)] 13
= (\x -> x*2 + 16) 13
= 13*2 + 16
= 26 + 16
= 42

Answer 2

foldr f z可以看作是用f替换列表的"cons"(:)，用z替换空列表。因此，这意味着 foldr f z [x1, x2 … xn ] 等价于 f x1 (f x2 ( ... (f xn z) … ))

[(*2), (+5)] 是 (:) (*2) ((:) (+5) []) 的语法糖，因此我们可以将其替换为：(.) (*2) ((.) (+5) (+3))，这是 (*2) . (+5) . (+3) 的冗长形式。因此这是一个函数。如果我们用这个函数和 13 作为参数创建一个函数应用程序，我们得到：

   ((*2) . (+5) . (+3)) 13
-> ((*2) . (+5)) 16
-> (*2) 21
-> 42

foldl f z [x1, x2 ... xn] 等价于 f (… (f (f z x1) x2) … ) x n。所以这里的意思是 foldl (.) (+3) [(*2), (+5)] 等同于 (.) ((.) (+3) (*2)) (+5)，或者更简洁的 (+3) . (*2) . (+5)。如果我们对 13 进行评估，我们将获得：

   ((+3) . (*2) . (+5)) 13
-> ((+3) . (*2)) 18
-> (+3) 36
-> 39

Answer 3

在 Haskell（和 lambda 演算）中你可以做 Eta reduction

在你展示的例子中，长的写法是：

foldr (\f h -> f . h) (\x -> x+3) [(\x -> x*2), (\x->x+5)] 13

现在您可以像这样一个一个地应用 Eta 减少：

(\f h -> f . h)
(\f -> (f.))
(.)

下一个：

(\x -> x+3)
(+3)

(\x -> x*2), (\x->x+5) 与 (+3)

非常相似

所以最后你得到了等效的表达式：

foldr (.) (+3) [(*2), (+5)]

这意味着，组合每个函数，当列表为空时，应用 (+3)

haskell 中的 foldr 函数在这种情况下如何工作？

How does the foldr function in haskell work in this case?

haskell

fold