Jan | FEB | Mar
| 15 |
2008 | 2009 | 2010
2 captures 15 Feb 09 - 18 Feb 09 |
| Close Help

# sjs

## geeky ramblings

## A Scheme parser in Haskell: Part 1

Posted by sjs
on Thursday, May 03
From Write Yourself a Scheme in 48 hours:

> Basically, a monad is a way of saying “there’s some extra information attached to this value, which most functions don’t need to worry about”. In this example, the “extra information” is the fact that this action performs IO, and the basic value is nothing, represented as “()”. Monadic values are often called “actions”, because the easiest way to think about the IO monad is a sequencing of actions that each might affect the outside world.

I really like this tutorial. I’m only on part 3.3 of 12, parsing, but I’m new to Haskell so I’m learning left, right & centre. The exercises are taking me hours of reading and experimenting, and it’s lots of fun! ghc’s errors are usually quite helpful and of course ghci is a big help as well.

I’m going to explain one of the exercises because converting between the various syntax for dealing with monads wasn’t plainly obvious to me. Perhaps I wasn’t paying enough attention to the docs I read. In any case if you’re interested in Haskell at all, I recommend the tutorial and if you’re stuck on exercise 3.3.1 like I was then come on back here. Whether you’re following the tutorial or not the point of this post should stand on its own with a basic knowledge of Haskell.

Last night I rewrote `parseNumber` using `do` and `>>=` (bind) notations (ex. 3.3.1). Here’s `parseNumber` using the `liftM` method given in the tutorial:

    parseNumber :: Parser LispVal
    parseNumber :: liftM (Number . read) $ many1 digit

Okay that’s pretty simple right? Let’s break it down, first looking at the right-hand side of the `$` operator, then the left.

- `many1 digit` reads as many decimal digits as it can.

- `Number . read` is a function composition just like we’re used to using in math. It applies `read` to its argument, then applies `Number` to that result.

- `liftM` is concisely and effectively defined elsewhere, and I’ll borrow their description:

> `liftM f m` lets a non-monadic function `f` operate on the contents of monad `m`

`liftM`’s type is also quite telling: `liftM :: (Monad m) => (a -> b) -> (m a -> m b)`

In a nutshell `liftM` turns a function from `a` to `b` to a function from a monad containing `a` to a monad containing `b`.

That results in a function on the left-hand side of `$`, which operates on and outputs a monad. The content of the input monad is a `String`. The content of the output monad is a `LispVal` (defined earlier in the tutorial). Specifically it is a `Number`.

The `$` acts similar to a pipe in `$FAVOURITE_SHELL`, and is right associative which means the expression on the right is passed to the expression (function) on the left. It’s exactly the same as `(liftM (Number . read)) (many1 digit)` except it looks cleaner. If you know LISP or Scheme (sadly I do not) then it’s analogous to the `apply` function.

So how does a Haskell newbie go about re-writing that using other notations which haven’t even been explained in the tutorial? Clearly one must search the web and read as much as they can until they understand enough to figure it out (which is one thing I like about the tutorial). If you’re lazy like me, here are 3 equivalent pieces of code for you to chew on. `parseNumber`’s type is `Parser LispVal` (Parser is a monad).

Familiar `liftM` method:

    parseNumber -> liftM (Number . read) $ many1 digit

Using `do` notation:

    parseNumber -> do digits <- many1 digit
                      return $ (Number . read) digits

If you’re thinking “Hey a `return`, I know that one!” then the devious masterminds behind Haskell are certainly laughing evilly right now. `return` simply wraps up it’s argument in a monad of some sort. In this case it’s the `Parser` monad. The `return` part may seem strange at first. Since `many1 digit` yields a monad why do we need to wrap anything? The answer is that using `<-` causes `digits` to contain a `String`, stripped out of the monad which resulted from `many1 digit`. Hence we no longer use `liftM` to make `(Number . read)` monads, and instead need to use `return` to properly wrap it back up in a monad.

In other words `liftM` eliminates the need to explicitly re-monadize the contents as is necessary using `do`.

Finally, using `>>=` (bind) notation:

    parseNumber -> many1 digit >>= \digits ->
                   return $ (Number . read) digits

At this point I don’t think this warrants much of an explanation. The syntactic sugar provided by `do` should be pretty obvious. Just in case it’s not, `>>=` passes the contents of its left argument (a monad) to the function on its right. Once again `return` is needed to wrap up the result and send it on its way.

When I first read about Haskell I was overwhelmed by not knowing anything, and not being able to apply my previous knowledge of programming to anything in Haskell. One piece of syntax at a time I am slowly able to understand more of the Haskell found in the wild.

I’m currently working on ex. 3.3.4, which is parsing R5RS compliant numbers (e.g. #o12345670, #xff, #d987). I’ll probably write something about that once I figure it out, but in the meantime if you have any hints I’m all ears.

Update #1: I should do more proof-reading if I’m going to try and explain things. I made some changes in wording.

- Tags: coding haskell
- Meta: permalink

##### Comments

Leave a response

1. Edward Kmett – May 11, 2007 @ 10:26 AM
   In your above example, you can view return as another function in the chain of functions to apply, yielding: parseNumber = many1 digit >>= return . Number . read or parseNumber = do digits <- many1 digit; return . Number . read $ digits of course, this is just unrolling the definition of liftM, so its not surprising.
2. sjs – May 11, 2007 @ 10:26 AM
   Ah, that makes perfect sense. Thanks for that. Every little bit helps my understanding of monads.
3. anonymous – May 29, 2007 @ 01:49 PM

   You might also want to know that for monads,

       liftM = fmap

   This is useful (at least for me), because I have different intuitions for liftM and fmap:

   I see liftM as a function lifting ordinary functions to monadic functions, while I think of (fmap f) as a function manipulating the “contents” of a monadic value using f, just like the ordinary map on lists manipulates the elements of lists.

   (Depending on context, I use both liftM and fmap.)

   In your case, I’d use fmap (this choice is completely subjective, of course), to stress that I just want to change the contents of the monadic return value of (many1 digits):

       fmap (Number . read) $ many1 digits

   Also, some prefer to write this using infix notation:

       Number . read `fmap` many1 digits

   This way you see that fmap can be tought of being ($), only modulo monadic stuff.

   BTW, fmap is useful on many other data structures, too:

       fmap f (Just x) = Just (f x)
       fmap f Nothing  = Nothing

       fmap f (Left  x) = Left x
       fmap f (Right x) = Right (f x)
       -- You need Control.Monad.Error for this one.

       fmap f xs = map f xs
       -- With xs :: [a]

   Happy Haskelling!