计算map的类型。文件夹`

Question

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

找出map . foldr类型的系统方法是什么？我知道如何为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]

Answer 2

map . foldr实际上是(.) map foldr。将(.)的类型添加到我们得到的混合中

        foldr :: Foldable t =>           (d -> (r -> r)) -> (r -> (t d -> r))
    map :: (i -> j) -> ([i] -> [j])
(.) ::    (   b     ->      c      ) -> (    a           ->     b            ) -> (a -> c)
-------------------------------------------------------------------------------------------
(.) map foldr :: Foldable t =>                                                    (a -> c)
    where                        a ~ d -> (r -> r)  
                                 c ~ [i] -> [j]
                                 b ~ r -> (t d -> r)
                                   ~ i ->      j
                                 -------------------
                                 r ~ i
                                 j ~       t d -> r
                                   ~       t d -> i

因此

map . foldr :: Foldable t => d -> (r -> r) -> [i] -> [j]
            ~  Foldable t => d -> (i -> i) -> [i] -> [t d -> i]
            -- or, renaming,
            ~  Foldable t => a -> (b -> b) -> [b] -> [t a -> b]