mono-traversable中的"concatMap“如何能够”拉出“常见的参数？

Question

我正在学习Haskell，正在为Yesod做一个简单的DB-seed程序时，我偶然发现了这个行为，我发现很难理解：

testFn :: Int -> Bool -> [Int]
testFn a b = if b then replicate 10 a else []

Yesod GHCI会话：

$ :t concatMap testFn [3]
concatMap testFn [3] :: Bool -> [Int]
$ (concatMap testFn [1,2,3]) True
[1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3]

不知何故，它能够从每个映射中“拉出”第二个"Bool“到单个curried参数中。

Standard base Prelude GHCI会话甚至拒绝编译这个表达式：

$ :t concatMap testFn [3]
error:
    • Couldn't match type 'Bool -> [Int]' with '[b]'
      Expected type: Int -> [b]
        Actual type: Int -> Bool -> [Int]
    • Probable cause: 'testFn' is applied to too few arguments
      In the first argument of 'concatMap', namely 'testFn'
      In the expression: concatMap testFn [3]

原来Yesod使用的是拥有自己的concatMap的mono-traversable库

$ :t concatMap
concatMap
  :: (MonoFoldable mono, Monoid m) =>
     (Element mono -> m) -> mono -> m

在我目前对Haskell的理解水平上，我不知道类型是如何在这里分布的。有人能给我解释一下(尽可能多的面向初学者)这个技巧是怎么做到的吗？上述testFn的哪个部分符合Element mono类型？

Answer 1

我们首先列出一些我们知道的类型。(为了简单起见，我们假设数字是Int --这实际上并不重要。)

testFn :: Int -> Bool -> [Int]
[1,2,3] :: [Int]
True :: Bool

(concatMap testFn [1,2,3]) True与concatMap testFn [1,2,3] True相同，因此concatMap必须有一个与所有这些参数匹配的类型：

concatMap :: (Int -> Bool -> [Int]) -> [Int] -> Bool -> ???

其中???是结果类型。请注意，由于关联性规则，->将关联到右侧，因此上面的类型与：

concatMap :: (Int -> (Bool -> [Int])) -> [Int] -> (Bool -> ???)

让我们在上面写一个通用类型。我添加了几个空格来标记相似性。

concatMap :: (MonoFoldable mono, Monoid m) =>
             (Element mono -> m              ) -> mono  -> m
concatMap :: (Int          -> (Bool -> [Int])) -> [Int] -> (Bool -> ???)

啊哈！如果我们选择m作为Bool -> [Int]，选择mono作为[Int]，就会有一个匹配。如果我们这样做了，我们确实满足了约束MonoFoldable mono, Monoid m (见下文)，而且我们也有Element mono ~ Int，所以所有的类型都会检查。

我们从???的定义中推断出m是[Int]。

关于约束:对于MonoFoldable [Int]来说，没什么好说的。[Int]显然是一种具有Int元素类型的类似列表的类型，这足以使它成为一个以Int作为其Element的MonaFoldable。

对于Monoid (Bool -> [Int])来说，这有点复杂。如果B是么半群，则任何函数类型A -> B都是么半群。这通过以逐点方式执行操作来实现。在我们的特定情况下，我们依赖于[Int]是一个么半群，我们得到：

mempty :: Bool -> [Int]
mempty = \_ -> []

(<>) :: (Bool -> [Int]) -> (Bool -> [Int]) -> (Bool -> [Int])
f <> g = \b -> f b ++ g b