9

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 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?

6

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
  • 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.