How does "concatMap" from mono-traversable is able to "pull out" common argument?

Question

I am learning Haskell and was doing a simple DB-seed program for Yesod when I stumbled upon this behavior which I find hard to understand:

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

Yesod GHCI session:

$ :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]

Somehow it was able to "pull" out that second "Bool" from each of mappings into a single curried argument.

Standard base Prelude GHCI session refuses to even compile this expression:

$ :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]

Turns out Yesod uses mono-traversable library which has its own concatMap:

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

At my current level of Haskell understanding I couldn't figure out how types are distributed here. Could someone explain to me (as much beginner oriented as possible) how this trick is done? What part of testFn above is conforming to Element mono type?

Answer 1

We start by listing some types we know. (We pretend that numbers are Int for simplicity -- this is not really relevant.)

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

(concatMap testFn [1,2,3]) True is the same as concatMap testFn [1,2,3] True, so concatMap must have a type matching all those arguments:

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

where ??? is the result type. Note that, because of the associativity rules, -> associates to the right, so the above typing is the same as:

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

Let's write the general type above that one. I am adding a few spaces to mark the similarity.

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

Ah-ha! We have a match if we choose m as Bool -> [Int], and mono as [Int]. If we do so, we do satisfy the constraints MonoFoldable mono, Monoid m (see below), and we also have Element mono ~ Int, so everything type checks.

We infer that ??? is [Int] from the definition of m.

About the constraints: for MonoFoldable [Int], there's little to say. [Int] is clearly a list-like type with an Int element type, and that's enough to make it into a MonaFoldable with Int as its Element.

For Monoid (Bool -> [Int]), it a bit more complex. We have that any function type A -> B is a monoid if B is a monoid. This follows by performing the operation in a pointwise fashion. In our specific case, we rely on [Int] being a monoid and we get:

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

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