More adventures in parsing

I received an interesting comment from Conal Elliott on my previous post on parsing. I have to admit I wasn’t sure I understood him at first, I’m still not sure I do, but I think I have an idea of what he means :-)

Basically my code is very sequential in that I use the do construct everywhere in the parsing code. Personally I thought that makes the parser very easy to read since the code very much mimics the structure of the maps file. I do realise the code isn’t very “functional” though so I thought I’d take Conal’s comments to heart and see what the result would be.

Let’s start with observation that every entity in a line is separated by a space. However some things are separated by other characters. So the first thing I did was write a higher-order function that first reads something, then reads a character and returns the first thing that was read:

Since space is used as a separator so often I added a short-cut for that:

Then I put that to use on parseAddress:

Modifying the other parsing functions using thenChar and thenSpace is straight forward.

I’m not entirely sure I understand what Conal meant with the part about liftM in his comment. I suspect his referring to the fact that I first read characters and then convert them in the “constructors”. By using liftM I can move the conversion “up in the code”. Here’s parseAddress after I’ve moved the calls to hexStr2Int:

After modifying the other parsing functions in a similar way I ended up with this:

Is this code more “functional”? Is it easier to read? You’ll have to be the judge of that…

Conal, if I got the intention of your comment completely wrong then feel free to tell me I’m an idiot ;-)

⟸ Adventures in parsing Comment to "A Look at Lua" ⟹

Holger

I just looked at the source of liftM2/3 and it seems that it basically just resolves to an expression in do-notation. So it’s just a shortcut and therefore should yield the same program.

Cale Gibbard

liftM2 guarantees an ordering on the monadic computation, because it’s defined like:

Though, that’s a little different from guaranteeing an order of evaluation – depending on the monad, the order of evaluation will vary. In any case, it shouldn’t be much different from what you originally had.

Another thing you might like to play around with, at least in your head, is the fact that:

and so on, which leads up to the style embodied by the Control.Applicative library, though if you really want to play around with that, you’ll need to write a quick instance of Applicative for GenParser, which should just consist of making pure = return and (<*>) = ap.

Twan van Laarhoven

The best way to make parsing code readable is to use Data.Applicative. Also, most people prefer where to let..in if possible. This gives something like:

Basicly (liftM# f x y z) can be written as f x <*> y <*> z.

Conal Elliott

yes, that’s exactly the direction i had in mind. once you switch from “do” style to “liftM#” style, it’s a simple step to replace the monad operators to applicative functor operators.

the previous comments have lost many operators in the blog conversion. is there a way to get code through safely, including operators that look html tags?

Twan van Laarhoven

&lt; should produce <. So: liftM3 f x y z == f <$> x <*> y <*> z

Magnus

Conal, ok, you’re one sneaky little b… ;-) I’ll have to look at the applicative operators to see what I think of them.

Yes, there is a way. I use markdown for writing my entries and it works in the comments as well. Besides that certain HTML tags seem to work. In particular <pre> works fine for code.

Leave a comment