7

如果

*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期望的参数才能(.)工作。但事实并非如此。那么问题是什么？

4

2 回答 2

19

如果您在签名中添加括号然后将它们排列起来，它可能会帮助您了解发生了什么：

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

现在应该很明显了，如果我们统一和，则输出replicate适合输入，在这种情况下，组合的输出类型是。concatMapba[b] -> [b]

于 2012-08-03T21:37:32.753 回答
9

困难可能来自混淆类型变量以及您如何推理类型统一。正如其他人所说，诀窍是考虑 (->) 是右关联的，这意味着您可以像这样排列事物（为每个签名创建新的类型变量以避免混淆）：

(.)       :: (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].

于 2012-08-03T22:19:21.400 回答