7 
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl step zero (x:xs) = foldl step (step zero x) xs
foldl _    zero []     = zero

我不太明白为什么 (a -> b -> a ) 返回a， (a -> b -> a) -> a -> [b] -> a返回a。我认为它应该是： (a -> b -> c ) -> a -> [b] -> c。有人可以根据下面的示例向我解释一下。谢谢！

foldl (+) 0 (1:2:3:[])
foldl (+) (0 + 1) (2:3:[])
foldl (+) ((0 + 1) + 2) (3:[])
foldl (+) (((0 + 1) + 2) + 3) ([])
foldl (+) (((0 + 1) + 2) + 3)
4

2 回答 2

14

a表示累加器值b的类型，表示输入中每个元素的类型。(a -> b -> a)是一个函数，它接受一个累加器值，列表中的某个项目，并返回一个可以传递到下一步的新累加器值。

初始值的类型必须是a函数的第一次调用可以接收累加器值。累加器函数必须接受a并返回一个a，以便可以将累加器值传递给折叠的每个步骤。fold 的最终值必须是 a a，因为这是最终调用 fold 函数将返回的累加器的类型。

(a -> b -> c) -> a -> [b] -> c不能表示折叠，因为折叠函数不采用c. 折叠函数的输入和输出必须是相同的类型，这样累加器才能传递到下一个折叠步骤。

让我们看一个例子，如果 fold 函数返回 a 会发生什么c。

f :: Integer -> Integer -> Bool   -- this is a valid (a -> b -> c)
f acc n = (acc + n) > 0

假设我们正在使用动态语言，并尝试使用f. 运行时会发生什么？

foldl f 0 [1]     ~ (0 + 1) > 0            == True :: Bool

foldl f 0 [1, 2]  ~ ((0 + 1) > 0) + 2) > 0 == error - no instance of (+) for Bool
                     \_________/   \
                          |         \
                         Bool      + Integer

您可以看到，如果您尝试使用不兼容的类型进行累积，则无法进行折叠。

于 2013-02-08T08:57:35.867 回答
2

折叠函数（类型(a -> b -> a)）的返回类型必须与其第一个输入的类型相同。这是因为，查看（几乎是正确的，除了最后一行，它不应该有foldl (+)）您给出的评估，折叠函数的先前调用的结果作为第一个输入传递给下一次调用。因此，类型必须匹配。在(a -> b -> c)第一个参数的类型中，结果只匹配 if a ~ c（类型相等），但在这种情况下，因为 a 和 c 相等，我们不妨将它们都称为 a。假设折叠函数返回 a 类型的东西，整个 foldl 调用的结果也将是 a 类型，因为它只是返回最后一次调用折叠函数的结果。

于 2013-02-08T08:50:27.960 回答