Using Monads for Control: Maybe it's worth a look?

So, after our last installment, describing the theory of monads, and the previous posts, which focused on representing things like state and I/O, I thought it was worth taking a moment to look at a different kind of thing that can be done with monads. We so often think of them as being state wrappers; and yet, that's only really a part of what we can get from them. Monads are ways of tying together almost anything that involves sequences.

In previous parts of this tutorial, we've seen the Maybe type. It's a useful type for all sorts of things where there might be a value. For example, a dictionary
lookup function would often be written something like:

lookup :: (Ord a) => Dictionary a b -> a -> Maybe b

You might expect (Ord a) => Dictionary a b -> a -> b, meaning a function from a dictionary and a value of type a to a value of type b. But that's not a great type definition for a lookup, because then what would the function return when the key isn't in the dictionary? Maybe gives us a way of handling that: if the key is included, we'll return Just b; otherwise, we'll return Nothing.

The problem with Maybe is that anytime you use it, you need to wrap
things up in pattern matches to check if a Nothing value was returned, and to extract a value if a Just was returned. That gets particularly messy if you have a sequence of things to be looked up. For example, imagine that we're writing a program for the police. They've got a license plate number, and they'd like to get the phone number of the person who owns the car with that plate. But the data is in different places: there's a list of license plate numbers associated with owners; and then there's the telephone book which has listings of peoples names and phone numbers. So here are some trivial implementations of the basic types and lookup functions:

>data LicensePlate = Plate String deriving (Eq,Show)
>
>getPlateOwner :: [(LicensePlate,String)] -> LicensePlate -> Maybe String
>getPlateOwner ((p, n):plates) plate 
>                  | p == plate = Just n
>                  | otherwise = getPlateOwner plates plate
>getPlateOwner [] _ = Nothing
>
>data PhoneNumber = Phone String String String deriving (Eq,Show)
>         -- area code, prefix, number
>getPhoneNumberForName :: [(PhoneNumber,String)] -> String -> Maybe PhoneNumber
>getPhoneNumberForName ((num,name):phonebook) person 
>                  | name==person = Just num
>                  | otherwise = getPhoneNumberForName phonebook person
>getPhoneNumberForName [] _ = Nothing

Suppose we had some databases for that:

>plateDB = [(Plate "abc", "Mark"),(Plate "h1a j2b", "Joe Random"), (Plate "u2k 5u1", "Jane Random")]
>
>phoneDB=[(Phone "321" "123" "3456", "Joe Random"), (Phone "345" "657" "3485", "Mark"), (Phone "588" "745" "1902", "Foo Bar")]

Now, suppose we wanted to write a lookup function from plate to phone number. The naive way would be:

>getPhoneForPlate :: [(LicensePlate,String)] ->  [(PhoneNumber,String)] -> LicensePlate -> Maybe PhoneNumber
>getPhoneForPlate ldb pdb lic =
>   let person = getPlateOwner ldb lic
>   in case person of
>         Just name -> getPhoneNumberForName pdb name
>         Nothing -> Nothing

Now, imagine if we wanted to add another layer - we'd need to add another let/case inside of the "Just name" case. The more we use Maybe, the messier it gets. But Maybe is a monad! So we could use:

>mGetPhoneForPlate ::  [(LicensePlate,String)] -> [(PhoneNumber,String)] -> LicensePlate -> Maybe PhoneNumber
>mGetPhoneForPlate ldb pdb lic =
>    do
>       name <- getPlateOwner ldb lic
>       phone <- getPhoneNumberForName pdb name
>       return phone

What happened here is that "Maybe" as a monad gives us a great way of chaining. Anywhere in the chain, if any step returns "Nothing", then the entire series will stop there, and return "Nothing". Any step where it returns "Just x", we can just capture the value as if there were no "Just". Suddenly chains of Maybe aren't a problem anymore.

An important thing to notice about this is that the monad is being used as a control structure. We've got a sequence of operations chained together in a monad. When we evaluate the monadic sequence, the implementation of the binding operator that combines monads actually does control flow management. Let's take a quick look at the internals of Maybe just to see how that's done:

instance Monad Maybe where
    return         = Just
    fail           = Nothing
    Nothing  >>= f = Nothing
    (Just x) >>= f = f x

Pretty simple, right? return really just wraps the value in a "Just". If there's an error along the way, "fail" will make the monad evaluate to "Nothing". And for chaining, "Nothing" chained with anything else results in "Nothing"; (Just x) chained with something unwraps x, and passes it to the next step in the chain. The control flow is captured in the pattern match between "Nothing" and "Just x" in the instance declaration of the ">>=" chaining operator.

This basic trick, of using the chaining operator to insert control flow into monadic sequences is an incredibly useful technique, which is used by a variety of really cool monads. Some examples that we'll look at in later installments are
monads for backtracking computation (like prolog); for non-deterministic computation; and for a really remarkably elegant way of building parsers.

(In fact, if you're not very lucky, and I have time over the next couple of days to finish it, on friday I'll post one of my own pathological programming languages, which has a parser implemented using the parsing monad. It's a language based on Post's tag systems, which form the most frustratingly simple Turing equivalent computing system that I know of.)