8

我试图理解为什么函数

map (filter fst)

有类型

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

如果过滤器必须接收一个返回 Bool-Type 的函数并且 fst 只返回元组的第一个元素，“过滤器 fst”如何工作？

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

谁能解释我？谢谢 ;）

4

6 回答 6

17

如果过滤器必须接收一个返回 Bool-Type 的函数并且 fst 只返回元组的第一个元素，“过滤器 fst”如何工作？

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

过滤器必须接收一个返回 Bool-Type 的函数

好的，让我们看看你传递了什么：fst. 是fst函数吗？是的，是的，所以我们已经完成了第一部分。它返回一个Bool吗？好吧，让我们看看它的作用：

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

因此，如果元组的第一个元素是 a Bool，那么是的，它确实返回一个布尔值！但是，如果元组的第一个元素不是 a Bool，则它不会并且将无法通过类型检查。

让我们再看看你提出的类型。我将更改类型变量的名称只是为了让事情更清楚：

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

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

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

最后，类型map为：

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

（再一次，我在这里重命名了类型变量，只是为了将它们与我们上面使用的变量区分开来，但请记住，只要它们在类型注释）

map (filter fst)将filter fst我们在上面定义的作为第一个参数传递给map. 将参数 ford和结果代入 fore我们可以看到这个函数一定是[(Bool, c)] -> [(Bool, c)]，换句话说，两者都是d和eare (Bool, c)。将它们插入函数中，我们得到最终类型：

map (filter fst) :: [[(Bool, c)]] -> [[(Bool, c)]]
于 2014-03-19T12:08:19.627 回答
2

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

于 2014-03-19T11:58:51.930 回答
1

由于在发布 danielpwright 的答案之前我已经写下了这个，所以我还是发布了它。我只是通过我对filter fst这里类型的思考过程。

首先，写下类型签名（更改 fst 使其类型变量名称不会与过滤器的名称冲突）：

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

匹配：(a -> Bool)_((b, c) -> b)

b必须是Bool，这意味着a必须是(Bool,c)

通过专门filter处理这些信息，它变成：

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

这导致

filter fst :: [(Bool, c)] -> [(Bool, c)]
于 2014-03-19T12:14:42.197 回答
1 
: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

我们完成了。

于 2014-03-19T11:59:36.257 回答
1

正如其他人所做的那样，我想在这里解决类型方程；但我想以更直观的方式将它们写下来，因此可以以更自动的方式执行推导。让我们来看看。

filter :: (  a   -> Bool) -> [a] -> [a]
fst    ::  (c,d) -> c              -- always use unique type var names, 
------------------------           --   rename freely but consistently
filter fst :: [a] -> [a],    a -> Bool  ~  (c,d) -> c
                             a ~ (c,d)  ,  Bool ~ c
                             a ~ (Bool,d)
           ---------------------------
           :: [(Bool,d)] -> [(Bool,d)]

纯机械的东西。：） 有了这个，

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

最终类型中的类型变量可以自由重命名以提高可读性（当然以一致的方式）。

我的答案添加到此处其他答案中已经显示的内容的唯一内容是这个建议（我认为这很重要）：如果您遵循这个简单的原则，将一件事写在另一件事下面，那么执行这些类型变得非常容易以非常机械、自动的方式统一（从而减少出错的可能性）。

有关这方面的另一个示例，包括实际的类型派生 Prolog 程序，请参阅Haskell：如何手动推断表达式的类型。

于 2014-03-20T15:43:59.627 回答
1

你真的只需要解决一些类型的方程。开始吧：

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

因此，以下类型方程的解在filter fst :: [a] -> [a]哪里：a

 a -> Bool = (b, c) -> b

这意味着

 a    = (b, c)
 Bool = b

这意味着

 a = (Bool, c)

因此，filter fst :: [(Bool, c)] -> [(Bool, c)]。

现在我们有：

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

因此，map (filter fst) :: [a] -> [b]其中a和b由以下类型方程给出：

a -> b = [(Bool, c)] -> [(Bool, c)]

这意味着

a = [(Bool, c)]
b = [(Bool, c)]

因此，map (filter fst) :: [[(Bool, c)]] -> [[(Bool, c)]]。

于 2014-03-19T16:10:38.657 回答