我感到困惑的功能`foldr`的哈斯克尔

Question

在书中“哈斯克尔编程”的类型，foldr相似的定义是：

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

我无法理解f非常好。

原因f适用于[a]，参数a在(a -> b -> b)是显而易见的。 的参数v具有类型b，但在最后b（甲 - >乙 - >b）和（a - >乙 - > B） - >乙 - >并[a] - >b是怪异。

是否表示功能f和foldr的型号为b？这怎么可能？

Answer 1

foldr f v列表

x1 : x2 : ... : [] 
-- i.e., in prefix notation 
(:) x1 ((:) x2 (... [])) 

映射到值

f x1 (f x2 (... v)) 

非正式地，它 “取代”（或 “解释”）的(:)构造与f，将[]构造与v。

从上面的公式可以看出，使用f的结果（很多次）作为f的第二个参数。因此它们必须具有相同的类型（在您的问题中为b）。 foldr的最终结果是最外面的f的结果，因此也与b一样。

Answer 2

如果你承认v有类型b，那么的foldr有结果有型b，因为v是foldr一个可能的结果：

foldr f v [] = v 

然后自foldr结果有为b，那么f的结果也必须为b，因为f结果可能为foldr结果：

-- f and foldr have to return the same type! 
foldr f v (x:xs) = f x (foldr f v xs)