代码之家 › 专栏 › 技术社区 › widgetycrank

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

fold lazy-evaluation haskell

1

widgetycrank · 技术社区 · 9 年前

我正在学习“Haskell编程从第一原则”。在“折叠列表”一章中,练习5f,

当我评估

foldr const 'a' [1..5]

我明白了

(Num Char)没有从文字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

我不明白为什么会有这种类型的错误。我猜编译器正在推断 x ( Num )基于类型 z ( Char ),但我看不出它在哪里建立了联系,因为 const 或 f 不需要它的两个参数是同一类型。

有什么想法吗?

4 回复 | 直到 9 年前

1

2

dfeuer 9 年前

好的,看看 foldr :: (a -> b -> b) -> b -> [a] -> b

从权利开始,你显然必须拥有 a 是的某个例子 Num 和 Enum (因为您使用 [1..5] )

下一步你进去 'a' 所以你有 b ~ Char

你终于有了 const 对于函数-和常量 const :: a -> b -> a -注意你现在必须拥有 a ~ b 因为你统一了

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

但这当然意味着 “a” 必须是的实例的值 号码 哪一个 Char 不是……这是你的错误(它抱怨1,因为从左边开始,问题就变得明显了)

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

所以现在你又有了 一 一些实例 号码 , b 必须再次 烧焦 但现在 常量 恰到好处 b 和 一 常量类型)

2

1

sepp2k 9 年前

foldl 和 foldr 援引 f 具有不同的参数顺序。这就是 折叠 电话 const x 'a' 但是 折叠 电话 const 'a' x 。后者的结果是“a”,这很好,但后者的结果为 x ,这是错误的,因为 x(x) 是一个 Int 结果应该与累加器的类型相同( Char ).

3

1

Rodrigo Ribeiro 9 年前

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

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

和 foldr 类型为:

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

申请时 折叠 到 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 类,但不是 Num 这就是你得到这个错误消息的原因。

4

1

Rufflewind 9 年前

正如其他人所说 foldl 和 foldr 是不同的。使用 flip const 相反:

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