为什么"map (filter fst)“类型[(Bool，a)]] -> [[(Bool，a)]”？

Question

我想弄明白为什么这个函数

map (filter fst)

有类型

[[(Bool, a)]] -> [[(Bool, a)]]

如果过滤器必须接收返回Bool类型的函数，而fst只返回元组的第一个元素，那么"filter fst“如何工作呢？

filter :: (a -> Bool) -> [a] -> [a]
fst :: (a, b) -> a

有人能解释我吗？(谢谢;)

Answer 1

如果过滤器必须接收返回Bool类型的函数，而fst只返回元组的第一个元素，那么"filter fst“如何工作呢？

从某种意义上说，你已经回答了你自己的问题！让我们把它分解：

过滤器必须接收返回Bool类型的函数。

好的，让我们看看您要传递的是什么：fst。fst是一个函数吗？是的，所以我们把第一部分弄下来了。它返回一个Bool吗？好吧，让我们看看它的作用：

fst只返回元组的第一个元素。

因此，如果元组的第一个元素是Bool，那么是的，它确实返回一个bool！但是，如果元组的第一个元素不是Bool，那么它不会，而且会使打字机失败。

让我们再看一看你提供的类型。我将更改类型变量的名称，以使事情更清楚：

filter :: (a -> Bool) -> [a] -> [a]
fst :: (b, c) -> b

fst接受一个(b, c)并返回一个b，过滤器期望一个函数接受一个a并返回一个Bool。我们正在传递fst，所以上面的a必须是(b, c)，因为这是fst的第一个参数。我们传递给filter的函数的返回值必须是Bool，因此上面的b必须是Bool。c可以是任何东西，因为它根本不被过滤器使用。将值替换为a和b给出了filter fst的最后一个类型：

filter fst :: [(Bool, c)] -> [(Bool, c)]

最后，map的类型是：

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

(同样，我在这里重命名了类型变量，只是为了区别于我们前面使用过的变量，但请记住，只要它们在类型注释的范围内是一致的，它们的名称实际上并不重要)

map (filter fst)将我们前面定义的filter fst作为第一个参数传递给map。用参数代替d和结果来代替e，我们可以看到这个函数必须是[(Bool, c)] -> [(Bool, c)]，换句话说，d和e都是(Bool, c)。将它们插入到最终类型的函数中：

map (filter fst) :: [[(Bool, c)]] -> [[(Bool, c)]]

Answer 2

fst是一个返回布尔值的函数，只要您将元组限制为第一个元素(第二个元素可以是任何东西，因此就可以是(Bool, a) )。

Answer 3

:t filter    -- (a -> Bool) -> [a] -> [a]
:t fst       -- (a,b) -> a

但是，我们也可以为fst交换类型变量以获得：

:t fst       -- (c,b) -> c

因此，filter的第一个参数具有a -> Bool类型，而fst本身是(c,b) -> c。现在我们尝试将其结合起来(我认为这被称为统一)：

1st arg of filter:  a     -> Bool
fst:                (c,b) -> c

由此，我们可以推断出c必须是Bool (因为右边必须相等)并获得：

1st arg of filter:  a        -> Bool
fst:                (Bool,b) -> Bool

根据上述，我们推断a必须是(Bool,b)，并获得：

1st arg of filter:  (Bool,b) -> Bool
fst:                (Bool,b) -> Bool

我们就完了。