3

有人知道haskell'foldr'使用函数的步骤吗？

GHCI 命令窗口：

foldr (\x y -> 2*x + y) 4 [5,6,7]

评估后的结果：

40

踏上这一步，

Prelude> foldr (\x y -> 2*x + y) 4 [5,6,7] 
6 * 2 + (7 * 2 + 4)
12 + 18 = 30
5 * 2 + 30 = 40 v
4

3 回答 3

7

foldr 的一种定义是：

foldr            :: (a -> b -> b) -> b -> [a] -> b
foldr f acc []     = acc
foldr f acc (x:xs) = f x (foldr f acc xs)

Haskell上的wikibook 关于 foldr （以及其他折叠）有一个很好的图表：

  :                         f
 / \                       / \
a   :       foldr f acc   a   f
   / \    ------------->     / \
  b   :                     b   f
     / \                       / \
    c  []                     c   acc

即a : b : c : []（只是[a, b, c]）变成f a (f b (f c acc))（再次，取自维基百科）。

因此，您的示例被评估为let f = (\x y -> 2*x + y) in f 5 (f 6 (f 7 4))（仅为简洁起见让绑定）。

于 2010-08-20T09:00:03.013 回答
0

[这应该是对德尔南言论的评论，但是太罗嗦了……]

lambdabotYoon，您可以在#haskell irc（例如在http://webchat.freenode.net/）上打开私人“对话” 。她有一个简单的反射能力，所以你可以输入无意义的字母，例如

    Yoon: > foldr (\x y -> 2*x + y) o [a,b,c,d]
lamdabot: 2 * a + (2 * b + (2 * c + (2 * d + o)))

这说明了评估的内容，但是正如 Edka 指出的那样，您可以从 say 中获得评估顺序的图片

     Yoon: > reverse (scanr (\x y -> 2*x + y) o [a,b,c,d])
lambdabot: [o,2 * d + o,2 * c + (2 * d + o),2 * b + (2 * c + (2 * d + o)),2 * a + (2 * b + (2 * c + (2 * d + o)))

我记得在玩 , , 和这个聪明的设备时留下了一些foldr很好foldl的教训scanr。scanl

于 2010-08-21T17:11:21.690 回答
0

您实际上可以很容易地为自己可视化它：

import Text.Printf

showOp f = f (printf "(%s op %s)") "0" ["1","2","3"]

然后

Main> showOp foldr
"(1 op (2 op (3 op 0)))"
Main> showOp foldl
"(((0 op 1) op 2) op 3)"
Main> showOp scanl
["0","(0 op 1)","((0 op 1) op 2)","(((0 op 1) op 2) op 3)"]
于 2010-08-21T00:06:20.797 回答