haskell - foldr (.) id 的类型

Question

我试图弄清楚表达式的类型:

foldr (.) id 

GHCI 给了我:

foldr (.) id :: Foldable t => t (b -> b) -> b -> b

我无法弄清楚这一点。文件夹类型为 Foldable t => (a -> b -> b) -> b -> t a -> b.所以它需要3个参数作为输入。所以我认为 foldr (.) id应该将单个参数作为输入。有人可以解释如何分析这种表达的类型吗？

Answer 1

类型Foldable t => t (b -> b) -> b -> b读作:

( Foldable t => ... ) 选择任何类似列表的“容器”类型 t ,

( t (b -> b) -> ... ) 然后提供 t 作为参数-函数容器b -> b ,

( b -> b ) 最终结果将是一个函数 b -> b .

所以，它只比“给我一个函数列表，我会产生一个函数”稍微通用一点。

事实上，当我们使用列表作为容器时:

foldr (.) id [f1,f2,f3,...,fn]

结果，根据 foldr 的定义， 在

f1 . (f2 . (f3 .  ... (fn . id) ...))

这是列表中所有函数的组成。

So i thought that foldr (.) id should take a single parameter as input.

确实如此:参数的类型为 t (b -> b) . Haskell 中的每个函数都接受一个参数作为输入。例如。

foo :: T -> U -> W -> Z

需要 T并返回一个函数 U -> W -> Z .
现在，我们也可以说 foo接受两个 T 类型的参数和 U并返回一个函数 W -> Z .或者它需要三个参数 T , U , 和 W , 并返回 Z .由于柯里化(Currying)，这些类型的解释之间没有真正的区别，因此我们可以选择最容易掌握的那个。

在您的情况下， foldr (.) id 的结果类型是 b -> b ，所以通常会解释第一个 b作为附加论据。但是，这并不能提供良好的直觉。更容易想到 b -> b是结果类型。

从技术上讲: foldr 的类型是(为清楚起见重命名变量)。

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

在 foldr (.) id ，我们可以看到第二个参数的类型是 id :: b -> b ，因此我们使用 c = (b -> b) ，就好像我们将上述类型专门化为:

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

现在，第一个参数的类型必须为 (.) :: (a -> (b -> b) -> (b -> b))类型检查。这只有在 a = (b -> b) 时才有可能。 .因此，我们再次特化。

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

这是最终类型:在此特化之后， foldr然后可以应用于 (.)和 id .

上述所有特化都是 GHC 从您的代码中自动推断出来的。本质上，GHC 选择 a和 c以唯一可以使您的代码类型检查的方式