Monoid instance resolution of `Int -> Int -> Ordering`

Question

I plan to showcase an example of the power of typeclasses in a small intro I'll give to Haskell tomorrow.

I thought I'd double check on what I was going to present because I'm not 100% confident.

So, let's say I have two functions:

firstSort :: Int -> Int -> Ordering
firstSort a b = compare (even a) (even b)

secondSort :: Int -> Int -> Ordering
secondSort = compare

Now, I can combine those two sorts thanks to their Monoid instances:

sort :: Int -> Int -> Ordering
sort = firstSort <> secondSort

Now what I'd like to confirm is the process used during the mappend of the two sorts.

From what I understand, it works this way:

• first the instance:

  instance Monoid b => Monoid (a -> b) where
          mempty _ = mempty
          mappend f g x = f x `mappend` g x
  

  is used. This is done by instanciating the a of this instance with (Int -> Int). Also, the declaration of mappend got me puzzled for some time since it takes 3 arguments instead of 2 but then I remembered that (a -> b) -> (a -> b) -> (a -> b) is actually the same as (a -> b) -> (a -> b) -> a -> b.

  Thanks to this instance we obtain that firstSort <> secondSort is:

  \a b -> (firstSort a b) <> (secondSort a b)
  

• then the instance:

  instance Monoid Ordering where
          mempty         = EQ
          LT `mappend` _ = LT
          EQ `mappend` y = y
          GT `mappend` _ = GT
  

  is used with the specified mappend on the results of firstSort and secondSort

So, to sum it up, it would match the Monoid b => Monoid (a -> b) instance with b = Ordering and a = (Int -> Int) and afterwards the Monoid Ordering instance.

Is that correct?

Answer 1

Yes. You've concluded correctly.

Since Int -> Int -> Ordering is curried, it can be seen as a function of one argument, which returns another function. I.e.:

Int -> (Int -> Ordering)

Hence the compiler resolves the Monoid instances in three steps:

 Value Type               | Monoid Instance
--------------------------|---------------------------
 Int -> (Int -> Ordering) | instance Monoid b => Monoid (a -> b)
 Int -> Ordering          | instance Monoid b => Monoid (a -> b)
 Ordering                 | instance Monoid Ordering

Answer 2

Let's see. I don't think the a that you want is (Int -> Int) because function types associate to the right when there are no parantheses. In your case, the types are

firstSort :: Int -> (Int -> Bool)
secondSort :: Int -> (Int -> Bool)

So, something interesting is going on here. When you concatenate the two functions, it's actually doing it twice! First, the a is just the first Int and b is the Int -> Bool, so we have to use the Monoid structure of Int -> Bool. But to do that we have to do the exact same thing again, so the a is Int and the b is Bool.

firstSort <> secondSort = \a -> (firstSort a) <> (secondSort a) 
                        = \a -> (\b -> (firstSort a b) <> (secondSort a b))

But the end result is still the same as the one you derived:

                        = \a b -> (firstSort a b) <> (secondSort a b)