派生推断类型的组合函数Haskell:具体(.)map uncurry

Question

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

我的考试学习指南有问题,而且我很难搞清楚.

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

我能够在大多数时间推导推断类型,但我仍然有点困惑.例如,我知道要获得(.)map uncurry的答案,您需要首先派生地图类型uncurry.我能做到这一点

鉴于以下类型

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

我将地图中的函数(a - > b)与uncurry统一起来

a = a ? b ? c
b = (a, b) ? c

然后答案是地图[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来自哪里或基本上是如何完成的.我认为我真正需要的是对一般类型统一的解释.统一两种类型的方法是什么？如何知道两种类型是否无法统一.

如果有人能够一步一步地解释如何导出(.)地图,我会非常感激.

Answer 1

导出类型签名的关键思想:

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,首先要统一的类型来自(.)和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> :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) ++ ([] ++ []))

并且只有一次使用,$所以我没有打扰它.

如果你喜欢,你可以转换操作符,如++以功能(++),但我并不相信,这将帮助你,所以我会离开它是,刚刚记住的第一个参数是向左.

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