1

这里有很多关于推导组合函数的推断类型的线程，但我仍然很困惑。我发现的所有帖子都没有给出关于如何统一类型的一般解释。

我的一份考试学习指南有问题，我无法弄清楚。

8) (.) map uncurry :: ________的推断类型是什么

我大部分时间都能推导出推断的类型，但我仍然有点困惑。例如，我知道要获得 (.) map uncurry 的答案，您需要首先导出 map uncurry 的类型。这是我能做到的

给定以下类型

map  :: (a -> b) -> [a] -> [b]
uncurry :: (a -> b -> c) -> (a, b) -> c

我用 uncurry 统一了 map 中的函数 (a -> b) 所以

a = a → b → c
b = (a, b) → c

然后答案是 map [a] -> [b] 的另一半，带有 a 和 b 的新值，所以

map uncurry :: [ a -> b -> c ] -> [ (a, b) -> c]

然后你需要统一

(.)  :: (b -> c) -> (a -> b) -> a -> c
map uncurry :: [ a -> b -> c ] -> [ (a, b) -> c]

答案应该是

(.) map uncurry :: (a -> b1 -> b) -> [(a, b1)] -> [b]

但我不明白 b1 来自哪里或基本上是如何完成的。我认为我真正需要的是对类型统一的一般解释。统一两种类型的方法是什么，我如何知道两种类型不能统一。

如果有人可以逐步解释如何导出 (.) map uncurry，我将不胜感激。

4

2 回答 2

6

派生类型签名的关键思想：

  1. 确保在开始之前获得运算符和函数的优先级。
    请注意，函数应用程序具有最高优先级并关联到左侧，因此：
  2. 第一个论点是最重要的——首先处理它，然后
  3. 在类型签名中，->关联到右侧。
  4. 一旦你有了第一个参数的类型，就在它出现的任何地方替换那个类型。

让我们来看看你的例子。

类型

(.)  :: (b -> c) -> (a -> b) -> a -> c
map  :: (a -> b) -> [a] -> [b]
uncurry :: (a -> b -> c) -> (a, b) -> c

给每个函数不重叠的类型名称

首先，这很令人困惑，因为有很多as 并且它们的意思并不相同，所以我每次都要用新字母重命名这些类型。

(.)  :: (b -> c) -> (a -> b) -> a -> c
map  :: (d -> e) -> [d] -> [e]
uncurry :: (f -> g -> h) -> (f, g) -> h

括号类型，关联到右边

(.)  :: (b -> c) -> ((a -> b) -> a -> c)
map  :: (d -> e) -> ([d] -> [e])
uncurry :: (f -> (g -> h)) -> ((f, g) -> h)

将第一个参数的类型与该参数的整个类型匹配

现在让我们看一下表达式(.) map uncurry。正如您现在已经意识到的那样，将运算符.放在括号中会将其转换为遵循正常函数规则的函数，因此 (.) map uncurry意味着((.) map) uncurry，并且要统一的第一个类型是 from(.)和map.

现在(.)有第一个参数(b->c)，所以(b->c)必须与类型统一map：

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

当我们替换时b ~ (d->e)，我们得到c ~ ([d]->[e])的类型是(.)：

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

所以map成为它的第一个参数，所以当我们提供它时它会从类型签名中消失，给出

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

请与 ghci 或 hugs 等口译员联系

Hugs> :t (.) map
(map .) :: (a -> b -> c) -> a -> [b] -> [c]

是的- 当我们由于->右关联而添加括号时，它们是相同的。

继续下一个论点

好的，所以现在我们有了

(.) map :: ((a -> (d->e)) -> (a -> ([d]->[e])))
uncurry :: (f -> (g -> h)) -> ((f, g) -> h)

现在匹配这两个第一个参数是非常诱人的，因为它们看起来相同，但是我们当然需要将第一个参数(.) map与整个类型匹配uncurry：

将第一个参数的类型与该参数的整个类型匹配

(.) map :: ((     a      -> (  d   -> e)) -> (a -> ([d]->[e])))
uncurry ::   (f->(g->h)) -> ((f,g) -> h)

给a ~ (f->(g->h)),d ~ (f,g)和e ~ h:

(.) map :: (((f->(g->h)) -> ((f,g)-> h)) -> ((f->(g->h)) -> ([(f,g)]->[h])))

并将其应用于 uncurry 给出

(.) map            uncurry               :: ((f->(g->h)) -> ([(f,g)]->[h])))

与口译员核实

Hugs> :t (.) map uncurry
map . uncurry :: (a -> b -> c) -> [(a,b)] -> [c]

太好了——我们做到了！

与运营商打交道

如果我们举这个例子length . map (.) $ repeat id ++ [] ++ []，我们将需要所有这些运算符的固定性，但我们可以先将函数应用程序括起来，因为它们优先：

length . map (.) $ repeat id ++ [] ++ []
length . (map (.)) $ (repeat id) ++ [] ++ []

将运算符按优先顺序排列

使用解释器的命令查找运算符的固定性:i，并将它们按顺序排列，最高的在前：

infixr 9 .
infixr 5 ++
infixr 0 $

最高优先级运算符.首先被括起来：

(length . (map (.))) $ (repeat id) ++ [] ++ []

然后++，与右侧相关联：

(length . (map (.))) $ ((repeat id) ++ ([] ++ []))

而且只有一种用途，$所以我没有打扰它。

如果您愿意，您可以将运算符 like 转换++为 functions (++)，但我完全不相信这会对您有所帮助，所以我会保留它，只需记住第一个参数在左边。

从最嵌套的括号开始通常会有所帮助。

于 2014-05-11T21:11:43.210 回答
0

(.) map uncurry相当于((.) map) uncurry。该map函数未应用于uncurry，而是传递给(.)。然后，您希望将其推断为函数的结果uncurry作为参数接收。

至于b1从哪里来，不要忘记类型变量名称并不重要，您可以重命名它们，只要您类似地重命名给定类型变量的所有出现即可。所以这：

(.) map uncurry :: (a -> b1 -> b) -> [(a, b1)] -> [b]

相当于：

(.) map uncurry :: (apple -> pear -> plum) -> [(apple, pear)] -> [plum]
于 2014-05-11T19:28:14.973 回答