为什么部分应用程序`foldr id` typecheck？

Question

在Haskell中,我不明白为什么部分应用程序会出现问题foldr id.

相关类型是

> :t foldr id
foldr id :: a -> [a -> a] -> a

> :t foldr
foldr :: (a -> b -> b) -> b -> [a] -> b

> :t id
id :: a -> a

第一个论点foldr是(a->b->b).相比之下,id是a->a.它们不应该兼容.

Answer 1

因为a -> b -> b实际上是a -> (b -> b).因为id :: a -> a,这a与b -> b我们结合,所以我们得到

id    ::  c ->    c                 -- type variable consistently renamed for uniqueness
foldr :: (a -> (b -> b)) -> b -> [  a   ] -> b        | c ~ a ,  c ~ b->b
foldr       id           :: b -> [  c   ] -> b
foldr       id           :: b -> [b -> b] -> b

就这样.

那它是做什么的？

foldr f z [x,y,...,n] = f x (f y (... (f n z)...))

foldr id z [x,y,...,n] =
    = id x (id y (... (id n z)...))
    =    x (   y (... (   n (id z))...))
    = (  x .   y . ...  . n . id ) z
    = foldr (.) id [x,y,...,n] z

因此foldr id = foldr ($) = flip (foldr (.) id),这是非常好的.列表中保存的函数全部叠加,因为输出和输入类型匹配.