为什么map具有这种类型？

Question

我试图找到函数 (.) map 的类型，但发现它实际上是 ((a -> d) -> (a -> e)) -> ([d] -> [e])。根据GHCI的说法，这是不正确的，因为它应该是 (.) map :: (a1 -> a2 -> b) -> a1 -> [a2] -> [b]。

我做错了什么？

- förschter

Answer 1

推导类型...

我们需要的材料如下：

(.) :: (b -> c) -> (a -> b) -> a -> c
map :: (d -> e) -> [d] -> [e]

(这里我使用了不同的类型标识符来避免任何混淆)。更详细的形式是(我们明确指出每个函数都只接受一个参数):

(.) :: (b -> c) -> ((a -> b) -> (a -> c))
map :: (d -> e) -> ([d] -> [e])

由于map是(.)的第一个参数，这意味着它的类型(d -> e) -> ([d] -> [e]) 应该与(.)函数的输入类型相匹配（即 b -> c）。因此，这意味着：

  b        -> c
~ (d -> e) -> ([d] -> [e])
------------------------------
b ~ (d -> e), c ~ ([d] -> [e])

那意味着(.) map的结果类型是：

(a -> b) -> (a -> c)

这相当于：

(a -> (d -> e)) -> (a -> ([d] -> [e]))

或更简洁一些：

(.) map :: (a -> d -> e) -> a -> [d] -> [e]

...以及它的实现

(.) 函数可以看作是 (.) f g == \x -> f (g x)。这意味着我们的函数

h = (.) map

等同于：

h f x = map (f x)

因此，它将函数f和对象x作为输入，然后以f x作为函数执行map。

从语义上讲，我们可以说我们制作了一个类型为a的“映射，其中必须注入'context'-objecct”的上下文对象。这个上下文被处理器考虑在内。如果我们想要应用多个具有小变化的map，并且因此首先传递“上下文对象”，那么这将很有用。当然，这是人类的一个解释。对于编译器而言，x可以具有任何用途、解释等等。

- Willem Van Onsem

Answer 2

您可能尝试通过查看定义来匹配函数。

Types of the two functions
(.) :: ((b -> c) -> (a -> b) -> a -> c)
map :: (d -> e) -> [d] -> [e]

然后尝试将d与b匹配，将e与c匹配。这给出了((a -> d) -> (a -> e)) -> ([d] -> [e])，现在可以将[d]与a匹配，将[e]与d匹配。但是这是不正确的，因为根据map的类型定义，e和d可以是不同的类型，即d可以是[e]类型，但不一定是。

找到此函数类型的正确方法是查看类型定义。

Types of the two functions
(.) :: ((b -> c) -> (a -> b) -> a -> c)
map :: (d -> e) -> [d] -> [e]

然后将(d -> e)与b匹配，将[d] -> [e]与c匹配，这样你就得到了(a -> (d -> e)) -> a -> ([d] -> [e])，去除多余的括号并重命名类型变量后，你会得到(a -> b -> c) -> a -> [b] -> [c]。这是GHCI给出的相同结果。

- förschter

Answer 3

当我不理解函数类型时，我会使用不同的字母来写出类型：

(.) :: (b -> c) -> (a -> b) -> a -> c
map :: (x -> y) -> [x] -> [y]

现在我们将map作为(.)的第一个参数提供，因此我们可以推断：

b -> c == (x -> y) -> [x] -> [y] -- by matching first arguments we get...
b == x -> y                      
c == [x] -> [y]

既然我们已经提供了(.)的第一个参数，整个b -> c部分就消失了。

(.) map :: (a -> b) -> a -> c                -- Using the above equations for b and c
(.) map :: (a -> x -> y) -> a -> [x] -> [y]  -- changing variables names
(.) map :: (a1 -> a2 -> b) -> a1 -> [a2] -> [b]

作为GHCi的绘图功能

- lsmor

---

通常波浪号（~）用于表示两种类型相同。不过加一分 :) - Willem Van Onsem

@WillemVanOnsem 不知道这个。谢谢分享 :) - lsmor