haskell - 计算 `map . foldr`的类型

Question

map :: (a -> b) -> [a] -> [b]
foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b

确定 map 类型的系统方法是什么。文件夹 ?我知道如何为 map foldr 做这件事，但是当涉及到组合时会感到困惑。

谢谢!

Answer 1

显然必须有一个系统的方法，否则 Haskell 编译器无法进行类型推断。

我们自己可以做到这一点的一种方法是逐步插入类型:

我们有以下类型:

(.) :: (b -> c) -> (a -> b) -> (a -> c)
map :: (a' -> b') -> [a'] -> [b']
foldr :: Foldable t => (a'' -> b'' -> b'') -> b'' -> t a'' -> b''

请注意，您必须为出现在不同签名中的类型选择不同的名称才能解决此问题。

<强>1。将 map 提供给 (.)

如果我们向 (.) 提供一个泛型函数 f，我们会得到以下类型:

(.) :: (b -> c) -> (a -> b) -> (a -> c)
(.) f :: (a -> b) -> (a -> c)
f :: (b -> c)

选择f作为map:

map :: (a' -> b') -> [a'] -> [b']

等于

map :: (a' -> b') -> ([a'] -> [b'])

因为 f 的类型是 (b -> c) 我们可以得出结论:

b :: (a' -> b')
c :: ([a'] -> [b'])

插入我们的推断类型:

(.) f :: (a -> b) -> (a -> c)
(.) map :: (a -> (a' -> b')) -> (a -> ([a'] -> [b']))

我们可以去掉一些括号:

(.) map :: (a -> (a' -> b')) -> a -> ([a'] -> [b'])
(.) map :: (a -> (a' -> b')) -> a -> [a'] -> [b']
(.) map :: (a -> a' -> b') -> a -> [a'] -> [b']

<强>2。将 foldr 提供给 (.) map

再次从提供通用函数 g 开始:

(.) map :: (a -> a' -> b') -> a -> [a'] -> [b']
(.) map g :: a -> [a'] -> [b']
g :: (a -> a' -> b')

选择g作为foldr:

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

等于

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

因为 g 的类型是 (a -> a' -> b') 我们可以得出结论:

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

插入我们的推断类型:

(.) map foldr :: a -> [a'] -> [b']
(.) map foldr :: Foldable t => (a'' -> b'' -> b'') -> [b''] -> [t a'' -> b'']

这与我们在向 ghci 询问类型时得到的类型相同:

> :t ((.) map foldr)
((.) map foldr) :: Foldable t => (a1 -> a2 -> a2) -> [a2] -> [t a1 -> a2]