不清楚foldl类型的定义

Question

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

我不太明白为什么(甲- >乙- > 一)返回一个,也(A - >乙- >) - > A - > [B] - > 一回一个.我认为应该是这样的:(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)

Answer 1

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

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

(a -> b -> c) -> a -> [b] -> c不能代表折叠,因为折叠功能不需要c.折叠功能的输入和输出必须是相同的类型,因此累加器可以传递到下一个折叠步骤.

让我们看一下如果fold函数返回一个会发生什么的例子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

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