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 library which has its own concatMap:

$ :t concatMapconcatMap  :: (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?


We start by listing some types we know. (We pretend that numbers are Int2020欧洲杯手机版注册 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 concatMap2020欧洲杯手机版注册 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  -> mconcatMap :: (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]2020欧洲杯手机版注册 being a monoid and we get:

mempty :: Bool -> [Int]mempty = \_ -> [](<>) :: (Bool -> [Int]) -> (Bool -> [Int]) -> (Bool -> [Int])f <> g = \b -> f b ++ g b
  • 1
    Great explanation! The way you've explained and aligned types is just what I wanted to see, thanks! – dimsuz 2 days ago

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.