Understanding 'instance Monad ((->) r)' by type inference

While reading source code of Control.Monad.Instances, I found I can’t understand ‘instance of Monad ((->) r)’, but after read Brent Yorgey’s reply in his blog post about The Typeclassopedia, he said, ‘the data constructor for (->) is called… lambda’, I suddenly found I CAN understand them by type inference. Here is how I do these.

There are two points:

• follow the types
• the data constructor for type constructor (->) is called lambda abstraction

This is the source code from Control.Monad.Instances:

instance Monad ((->) r) where
        return = const
        f >>= k = \r -> k (f r) r

The case of return is trivial. Look at it’s type first: return :: (Monad m) => a -> m a, so for ‘instance ((->) r)’, we have m = (->) r then

	  a -> m a
	= a -> ((->) r a)
	= a -> r -> a

Now look at const’s type: const :: a -> b -> a, exactly what we want. But what we got from ‘return a’? It is

        return a = (->) r a     -- misuse (->) at here
                 = \r -> a      -- data constructor of (->) is lambda
                 = \_ -> a

this is exactly what we got from ‘const a’, i.e. const a = \_ -> a

(>>=) is a bit complicate, but if you follow its type, you can understand it pretty easily.

Let’s look at it’s type first:

(>>=) :: (Monad m) => m a -> (a -> m b) -> m b

As before, for ‘instance ((->) r)’, we have m = (->) r, then

        f :: m a = (->) r a
        k :: a -> m b = a -> ((->) r b) = a -> r -> b

and suppose

        f r = a
        k a r = b

then we have

        f >>= k = \r -> k (f r) r
                = \r -> k a r
                = \r -> b
                = (->) r b      -- misuse of (->)
                = m b

Err..a bit misuse of (->) and didn’t distinguish type variables and normal variables, but it works for me. If you have the similar difficult to understanding ‘instance Monad ((->) r)’, I hope these work for you too.

About these ads