计算 `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 =>           (a -> (r->r)) -> (r -> (t a -> r))
    map :: (i -> j) -> ([i] -> [j])
(.) ::    (   b     ->      c      ) -> (    d         ->     b            ) -> (d -> c)
-----------------------------------------------------------------------------------------
--            4             2                1                3
-----------------------------------------------------------------------------------------
(.) map foldr :: Foldable t =>                                                  (d -> c)
    where                        d ~ a -> (r -> r)       -- 1
                                 c ~ [i] -> [j]          -- 2
                                 b ~ r -> (t a -> r)     -- 3
                                   ~ i ->      j         -- 4
                                 -------------------
                                 i ~ r                   -- 5
                                 j ~       t a -> r      -- 6

因此

map . foldr :: Foldable t => a -> (r -> r) -> [i] -> [j]          -- by 1,2
            ~  Foldable t => a -> (r -> r) -> [r] -> [t a -> r]   -- by 5,6

这里我们使用了application类型推导规则，

     f   :: A -> B
       x :: A
    ---------------
     f x ::      B

（在逻辑上也称为 modus ponens）。

我们还可以使用组合类型推导规则，它是专用于 (.) 的应用程序规则，或者等效地 (>>>) = flip (.):

           g ::      B -> C
     f       :: A -> B
    ------------------------
     f >>> g :: A ->      C
     g  .  f :: A ->      C

为了适应这个模式，我们写下类型有点不同，并得到结果立即:

          map ::                                (i ->      j    ) -> ([i] -> [    j   ])
foldr         :: Foldable t => (a -> (r->r)) -> (r -> (t a -> r))
------------------------------------------------------------------------------------
foldr >>> map :: Foldable t => (a -> (r->r)) ->                       [r] -> [t a -> r]
map  .  foldr :: Foldable t => (a -> (r->r)) ->                       [r] -> [t a -> r]

这样更直观。

Answer 3

好的，与其使用自动方法来推断类型，我想也许您会对更直观的答案感兴趣：

我相信你知道，map . foldr 等同于 (\x -> map (foldr x))。让我们从那个开始吧。

x 的类型应该是什么？嗯，因为它是 foldr 的第一个参数，它应该看起来像一个函数，它接受一些值、一些累加器和 return 与累加器相同类型的东西（根据 [=17= 的定义） ]).因此：

x :: (a -> b -> b)

现在我们有了第一个参数的类型，让我们看看剩下的。

一旦应用 (foldr x)，我们得到一个函数，该函数仍然等待初始累加器值，然后等待任何可折叠类型，并且 returns 是与累加器相同类型的值（例如，列表中每个元素的总和）。

所以(foldr x)的类型应该是

Foldable t => b -> t a -> b

好的，但我们还没有完成，让我们看看现在使用 map 会发生什么。

map 应该首先被赋予一个函数（根据定义）。 (foldr x) 的 return 值被视为那个，这意味着 map 的这种使用认为 (b -> t a -> b) 是需要应用于列表的每个元素的函数类型。

也许写成(b -> (t a -> b))更清楚。因此，这种 map 的使用考虑到它被赋予了一个接受 b 类型输入的函数，并且 returns 是一个本身接受可折叠 a 和 returns a b 的函数.

好的，我们快到了。现在，map 仍然需要另一个参数：一个列表，其中的元素与它将应用的函数的输入类型相同。因此，由于我们要应用的函数（(foldr x) 的结果）采用 b，因此我们对 map 的使用将采用 [b]。

所以现在我们有：

 (a -> b -> b) -> [b] -> …

我们只是缺少那个函数组合的输出值的类型，也就是这个具体使用map的输出值的类型。由于与 map return 一起应用的函数是 (t a -> b) 类型的东西，那么我们显然 return 的东西列表将是 [t a -> b].[=32= 类型的东西]

所以最后你有

Foldable t => (a -> b -> b) -> [b] -> [t a -> b]

作为 map . foldr 的类型。

计算 `map 的类型。文件夹`

Calculating the type of `map . foldr`

haskell

types

function-composition