Haskell:功能组合刚刚损坏了我的大脑

Question

如果

*Main> :t concatMap
concatMap :: (a -> [b]) -> [a] -> [b]

和

*Main> :t replicate
replicate :: Int -> a -> [a]

那怎么办呢？

*Main> :t concatMap . replicate
concatMap . replicate :: Int -> [b] -> [b]

给定:

*Main> :t (.)
(.) :: (b -> c) -> (a -> b) -> a -> c

？

我的意思是,我对函数组合的理解是replicate应该返回任何concatMap期望作为参数才能(.)工作.但事实并非如此.那捕获的是什么？

Answer 1

如果您在签名中添加括号然后将它们排成一行,它可能会帮助您查看正在发生的事情:

replicate :: Int -> (a -> [a])
concatMap ::        (a -> [b]) -> ([a] -> [b])

现在,应该是相当明显的是,输出replicate适合的输入concatMap,如果我们统一b和a,在这种情况下,该组合物的输出类型[b] -> [b].

Answer 2

困难可能来自混淆类型变量以及您如何推理类型统一.诀窍就是像其他人所说的那样考虑( - >)是右关联的,这意味着你可以像这样排序(为每个签名创建新的类型变量以避免混淆):

(.)       :: (b         ->  c         ) -> (a    -> b        )  -> a -> c
concatMap :: (q -> [r]) -> ([q] -> [r])
replicate ::                               (Int  -> (s -> [s])

这基本上给了我们一些我们需要解决的限制.假设"a~b"表示"a与b的类型相同"或等效地"a可以用b代替".

从上面可以推断出以下事实:

a ~ Int
b ~ (q -> [r]) ~ (s -> [s])
c ~ ([q] -> [r])

但是b的两个等价物告诉我们

(q -> [r]) ~ (s -> [s])

这需要

q ~ s and [r] ~ [s]

那么我们将c重写为:

c ~ ([q] -> [r]) ==> ([s] -> [s]))

将a和c的替换插回到原始类型(.)中,并应用两个函数

a -> c ~ Int -> ([s] -> [s]) 

当然现在以ghci报告的形式:Int -> [b] -> [b].