Everything About Mathematics, Functional Programming, and Haskell

Understanding ‘instance Monad ((->) r)’ by type inference

with 2 comments

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.


Written by Lee Duhem

June 7, 2009 at 4:04 pm

Posted in Haskell

Tagged with ,

2 Responses

Subscribe to comments with RSS.

  1. Probably it should be
    f >>= k = \r -> k (f r) r
    = \r -> k a r
    instead of
    f >>= k = \r -> k (f r) r
    = \r -> a r


    December 5, 2012 at 10:19 pm

    • Yes, you are right.

      Thanks for your correction, the original post has been updated.

      Lee Duhem

      December 6, 2012 at 1:34 am

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: