Haskell foldr 导致类型错误，而 foldl 没有

Question

我正在处理 "Haskell Programming From First Principles"。在关于折叠列表的章节中，练习 5f，

当我评估

foldr const 'a' [1..5]

我明白了

No instance for (Num Char) arising from the literal ‘1’

但是，

foldl const 'a' [1..5]

我得到 'a'.

我知道折叠是懒惰的，foldr 不会穿过书脊而 foldl 会。但即使查看 foldr 和 foldl 的定义，

foldr f z []     = z 
foldr f z (x:xs) = f x (foldr f z xs) 

foldl f z []     = z                  
foldl f z (x:xs) = foldl f (f z x) xs

我不明白为什么会出现这种类型错误。我猜编译器是根据 z (Char) 的类型推断 x (Num) 的类型，但我看不到它绘制的位置连接，因为 const 或 f 不要求它的两个参数是同一类型。

有什么想法吗？

Answer 1

ok 看看类型foldr :: (a -> b -> b) -> b -> [a] -> b

从右边开始你显然必须有 a 是 Num 和 Enum 的某个实例（因为你使用 [1..5]）

接下来你传入 'a' 所以你有 b ~ Char

最后你有函数 const - const 是 const :: a -> b -> a - 注意你现在必须有 a ~ b 因为你统一

a -> b -> b
a -> b -> a
        ^^^^^

但这当然意味着 'a' 必须是 Num 的一个实例的值，而 Char 不是......这是你的错误（它抱怨1 因为从左开始而不是问题变得明显的地方）

foldl 另一边有 foldl :: (b -> a -> b) -> b -> [a] -> b

所以现在你又遇到了 a Num 的一些实例，b 必须再次成为 Char 但现在 const 正好适合（只需切换b and a in the type of const)

Answer 2

foldl 和 foldr 使用不同的参数顺序调用 f。即 foldr 调用 const x 'a'，但 foldl 调用 const 'a' x。后者的结果是'a'，没问题，但是后者的结果是x，这是错误的，因为x是一个Int，结果应该是与累加器 (Char).

具有相同的类型

Answer 3

这是一个打字问题。 foldl 的类型是

foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b

和foldr类型是：

foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

当您将 foldr 应用于 const 时，您会得到：

foldr const :: Foldable t => b -> t b -> b

接下来，您提供 'a' 参数，您将得到

(foldr const 'a') :: Foldable t => t Char -> Char

因此，当您将 [1..5] 作为参数传递时，它会尝试将 t Char 与 (Enum a, Num a) => [a] 统一起来。类型 Char 是 Enum class 但不是 Num 的实例，这就是您收到此错误消息的原因。

Answer 4

正如其他人所说，foldl 和 foldr 中参数的顺序不同。使用 flip const 代替：

> foldr (flip const) 'a' [1..5]
'a'

Haskell foldr 导致类型错误，而 foldl 没有

Haskell foldr results in type error while foldl doesn't

haskell

lazy-evaluation

fold