I've been using haskell for about a year now, and thought I was really beginning to get a handle on this monad thing. Other than a strange name, and confusing C programmers with the keyword return that doesn't return, they looked like they were just a way of connecting things together, kinda like function composition. In fact, I found myself frequently writing code like:
> goldbach = > let primes = sieve [2..] > where sieve (p:xs) = p : sieve [x | x<-xs, x `mod` p /= 0] > p100 = takeWhile (<100) primes > pairs = [x+y | x<-p100, y<-p100] > evens = [4,6..100] :: [Int] > isPair x = x `elem` pairs > checkEvens = map isPair evens > conjecture = all id checkEvens > in conjecture
Here function composition, (not) cleverly disguised as a bunch of lets that accumulate, acts as the bind operator, providing sequencing. What I mean by this is that conjecture depends on checkEvens, which depends on isPair and evens, which depends on pairs, which depends on p100, which depends on primes, so even though the order of evaluation isn't explicit in pure functions, it is easy to write code so that in fact it is, by building up to the final answer in little pieces that depend on each other. With this in mind, even the Maybe monad seemed pretty straightforward, after it is is defined as:
> data Maybe a = Nothing | Just a > > instance Monad Maybe where > (Just x) >>= k = k x > Nothing >>= _ = Nothing > return x = Just x
You just have to remember that k is a function that takes an x to a Maybe y like:
> k :: Int -> Maybe String > k x = if x == 0 then Nothing else Just "Something"
So what happens if we bind Nothing with k? Well the Monad rule above which says that: Nothing >>= _ = Nothing means Nothing bound to anything still results in Nothing, so Nothing >>= k equals Nothing. What about Just 1 bound with k, well the Monad rule above, (Just x) >>= k = k x means apply the function k to 1, which since 1 /= 0 returns Just "Something". We can continue along, binding the output of k with another function, say k1, as long as the type of k1 is String -> Maybe whatever. So the analogy of binding with function composition is not really that far off.
In fact, with just a little more complicated binding, even the list Monad
> instance Monad [] where > m >>= k = concat (map k m) > return x = [x]
is just a variation of this theme. The binding now specified by m >>= k = concat (map k m) So the next monad I took a look at was the Reader Monad. Looking through the source for Reader.hs, I came across:
> newtype Reader r a = Reader { runReader :: r -> a } > instance Monad (Reader r) where > return a = Reader $ \_ -> a > m >>= k = Reader $ \r -> runReader (k (runReader m r)) r
As Raymond's father used to say, Holy Crap! If this code is perfectly clear to you, then you can skip the rest of this article, for I doubt you will learn anything new. If not, read on, and I hope I can make it a little clearer for you what is going on here.
The first thing that confused me was the newtype constructor. We have a Reader on the left hand side with two arguments, and a Reader on the right hand side with what looks like a record that has a variable in it called runReader. Huh? Also, I see the following code somewhere:
> r1 :: Reader Int String > r1 = do > a <- ask > return $ show (a+1) > test1 = putStrLn $ runReader r1 1
which dutifully prints 2. But!, again Reader has two arguments, one is an Int and one is a String, and now runReader isn't a field in a Record type but it looks like a function of two arguments as well. I'm very confused.
Maybe I'm just not smarter than the average bear, or maybe there are others out there who find this state of affairs similarly confusing, so lets see if we can dissect this stuff and make some sense of it.
1. The Reader on the left hand side is a type constructor. It is what you use when you write type signatures. In that sense it is like Int or String or Maybe. The Reader on the right hand side is what you use to make some data of type Reader (the left hand side). It is called a data constructor. I think the best way to keep these straight is to remember Maybe. In the definition of k above, the type signature told us that k takes Int and returns a Maybe String. Those are all type constructors. To make a Maybe String, the k function returns either a Nothing, or a Just x, where x is a string. The Nothing and Just are data constructors (really just functions) whose results are Maybes. We have every right to rename, say Just to Maybe, and all we will do is make things more confusing, but still legal. Then Maybe would have two meanings, one as (still) a type constructor, and another (now) as an data constructor. Well, that is what we have done with Reader. The Reader on the right hand side is a data constructor. Perhaps we would have been better off if it had been called ReaderData instead of Reader, but it wasn't, so get used to it. Even though it is the same word, its meaning is totally different on each side of the newtype declaration.
2. Okay, so why is there a record on the right hand side of the newtype constructor? Normally we see record types like this:
> data Birthday = BirthdayData { > month :: Int, > day :: Int, > year :: Int }
and we think of them as just variables ... parts of a Birthday. But in reality, they are functions (called selector functions). They are functions that take some Birthday data, and return an Int. So if you had:
> henry = BirthdayData 6 15 1954 > howOldIsHenry = 2009 - (year henry)
howOldIsHenry would return 55. (Am I really that old?) and year in the definition of howOldIsHenry is actually a function, that takes a Birthday data type, which you can construct by calling the BirthdayData data constructor with 3 integers, and returns the year portion of the Birthday. So please remove the imperative mind set that what is inside a Record type is a bunch of variables, it as actually a bunch of functions that operate on the data type.
3. Okay, so what about that (e -> a) on the right hand side. Remember that functions are first class objects in haskell. They are data, just like Ints, Strings, or anything else. As such, they need a type constructor, and that type constructor is spelled (->). We usually write it in its infix form, so if you want to describe the type constructor of a function from a to b, you would write (a->b), though you are perfectly free to write the more confusing version of ((->) a b) if you desire. Now returning to the newtype definition above, well, whole thing is really a shortcut way of writing:
> newtype Reader e a = Reader (e->a) > runReader (Reader f) x = f x
I think this is much clearer. It tells us that a Reader type constructor takes two type parameters, an e and an a. You create some Reader data by suppling a function (f) which takes an e to an a. You then wrap that function (f) inside an data constructor (confusingly also named Reader) such that if you provide the (Reader f) thing to runReader, along with another argument (x) of type e, you will get back f x (f of x) with returns something of type a.
We can see this in action with the following code:
> r2 :: Reader Int String > r2 = > let f x = show (x+1) > in Reader f > > test2 = putStrLn $ runReader r2 1
which again prints out 2. Look ma, no monads........yet. So while the type of r2 is Reader Int String, looking at it we see that it is really a function (f) from an Int -> String, wrapped inside a Reader data constructor. Okay, I hope this has cleared up the confusion surrounding the type constructor of a Reader. At least it did for me once I figured it all out. Now let's move on the the functions that make Reader a Monad. The line that needs serious decoding is:
> m >>= k = Reader $ \r -> runReader (k (runReader m r)) r
But, before we get to that, let's understand why return is defined as:
> return a = Reader $ \_ -> a
Now, the point of having a Reader is so that we can have some kind of environment hanging around in the background, without having to pass it around to all of our functions explicitly. Once we've set up this environment, which can be any arbitrarily complicated data structure, we can reference it with the ask function while we are running inside the Reader Monad. In the example above, the environment was a simple Int value, but in general it could be contents of every file on your computer. (though that might be a wee bit large.) The great thing about this is that it gives you, in a sense, access to global variables in a controlled local (Reader) environment. Now remember, runReader takes a function, f, which has access to an environment, e, and returns a value, a. That function may or may not care what is in it's environment. It is perfectly free to ignore it's environment if it wants to. A function which ignores its environment, and always returns the same result is known as the constant function, written const in haskell. (const :: a -> b -> a) Now consider the meaning of return for Monads. It must take an arbitrary data type, a, and inject it into the Monad. In the Reader monad, if we want the result of running the reader to be a, then we must create a function that takes it's environment e as an input, ignores it, and returns a as its result. Haskell has already provided us with such a function, and if we rewrite the definition of return above as:
> return a = Reader (const a)
we will get 1 back when we say: runReader (return 1) "anything" Just as we would if we said: runReader (Reader (const 1)) "anything" all return does is wrap the constant function inside a Reader data constructor. The constant functions ignores it environment, which in this case is the string "anything".
Okay, now lets move on to deciphering:
> m >>= k = Reader $ \r -> runReader (k (runReader m r)) r
I think this would be a lot clearer if it were rewritten in an equivalent form like:
> (Reader f1) >>= f2 = Reader $ \e -> runReader (f2 (f1 e)) e
now there is one less runReader to deal with, and the idea that we are dealing with two different functions is a little more obvious. To understand this, remember that the purpose of >>= is to bind together a Monad with a function that returns a Monad. Also recall that runReader take two arguments, a function to run and and environment to carry around. Now working from the inside out, we see f1 is a function. Thanks to pattern matching, we have extracted it from the Reader data constructor and named it f1. Now f1 takes its environment e, and returns an a. But where does this environment magically come from? Well, even if we have a long sequence of operations bound together in our Reader Monad, say f1 >>= f2 >>= f3 ... >>= fn, at some point we are going to take all of them and say runReader (f1 >>= f2 >>= f3 ... >>= fn) environment where environment will be the argument supplied to f1, which gets passed on to f2 etc. That argument shows up as e in the definition above. So f1 takes that e and returns an a. Let's rewrite the above with this in mind:
> (Reader f1) >>= f2 = Reader $ \e -> runReader (f2 a) e
Now what is f2? f2 is a function that takes an a and returns a Reader b. After all, that is what binding is all about. Let's make that substitution.
> (Reader f1) >>= f2 = Reader $ \e -> runReader (Reader b) e
Now what does runReader (Reader b) e do? Reader b is a function that takes an e and returns a c, (c does not have to be the same type as either a or b). runReader takes that function, supplies the e and returns the c. Let's rewrite again:
> (Reader f1) >>= f2 = Reader $ \e -> c
but this is the same as:
> (Reader f1) >>= f2 = Reader (const c)
which if you supply to runReader, along with an environment, will return c, where I mean return in the sense of C, and not in the sense of Monad. So, the definition of bind is a way of chaining all of these functions together in such a way that the externally supplied environment e is always the first argument to the functions we create. Pretty tricky, I must say.
So what have we learned? For me a couple of things. One, is you have to be very careful about keeping straight when something is a type constructor, like Maybe, and when it is an data constructor, like Nothing or Just, especially when it uses the same name, like Reader. Next, banish your C concepts that Records are lists of variables. They are functions that can do arbitrary things once they peel off their data constructor. Finally, when you find a complicated expression that is difficult to understand, work from the inside out, figure out what the inputs and outputs are, and substitute them in the expression to try to simplify it. Eventually it should become obvious.
This file is also available as an lhs file if you want to play with it.
Sitemap
Go up to Haskell Go up to Home Page of Nadine Loves Henry
Go back to Solving Project Euler Problem 191 Continue with A Tale of Two Approaches