Aha-one-liners

I’ve been working with computers for more than seven years now and before that I spent five and a half years in university studying computer science and engineering. During these years I’ve learnt a lot and had many aha-moments. However, since starting learning Haskell I’ve had aha-moments that manifest themselves in a single line of code. This has never happened before. Ever! I’m not sure what that says about Haskell. Maybe it’s computer science distilled, who knows?

Anyway, my latest aha-one-liner is this:

liftM dec $ sequence $ map (flip M.lookup decodeMap) s

I’ll try to recount how I got to it.

When writing dataenc I wrote a function decode :: String -> [Word8]. In a discussion on the Haskell libraries list apfelmus pointed out the necessity of allowing decode to fail. The obvious solution is to change the type to String -> Maybe [Word8].

The decoding is done using a look-up table, with some twiddling of bits to get the original data back from the encoded string. The first version used ! to do the lookup, but when this fails it throws an exception. There have been many emails on Haskell Cafe and several articles written on exceptions in Haskell, and as anyone who’s read them know: it’s better to avoid ever getting exceptions than dealing with them (I suspect this is true for any language). The function lookup offers a nice way of looking up a value without risking getting an exception. By mapping it over the string I end up with a list of possible values ([Maybe Word8]). The next step was to find a function that converts this list of possible values to possibly a list (Maybe [Word8]). sequence is just that function. The most important thing is that a single Nothing in the list of possible values results in a result of Nothing from sequence too. At this point I have a list of values, e.g. Just [1,2,3], or Nothing. All that’s left to do now is the bit twiddling part, and that’s of course what lifting dec does, and of course lifting dec into Nothing produces Nothing.

So, what was my aha-moment in all this?

Well, there were actually two things. First, it was the realisation that instead of using a function that can throw an exception (!) I could use a function that allows for failure in a controlled way (lookup). Second, by using the right type (Maybe) I can write my function as if failure doesn’t exist.

Why doesn’t all programming languages make it this easy?

[Edited 24-10-2007]: Spelling and grammar.

Share

9 Comments

  1. Sorry, but it is not trivial at all to get the formatting right.

    mapM f = sequence . map f

    liftM can be replaced by the more abstract fmap, or even better: the applicative combinator <$>.

    And we can strip flip by using a section:

    dec <$> mapM (`M.lookup` decodeMap) s

  2. Actually, that ‘sequence $ map (…) …’ bit is used quite frequently for mapping, when the function of map results in a monadic value. The prelude defines ‘mapM’ for this situation.

  3. You could also use mapM in place of your combination of sequence and map. I think of it as “map, sequenced within the monad”. If you think about how IO would use it (“do each of these operations in sequence, collecting the results”) it makes the translation into the Maybe monad more obvious.

    I’d maybe write your code as as: decode = liftM dec . mapM (flip M.lookup decodeMap)

  4. re: I can write my function as if failure doesn’t exist.

    Right! The title of the paper says it all: “How to convert failure into a list of successes.”

    Maybe is like the list monad except that (:) on anything other than [] is a no-op.

  5. mnislaih, I took the liberty of deleting the “failed” comments. I know that markdown isn’t the most commonly used markup, but it deserves to be. :) The preview functionality is your friend. On to the contents of your comment. Using fmap or <$> would indeed make it even shorter and sweeter. I suspect I’ll have to play a bit more with Haskell, and read up on what Control.Applicative has to offer.

    Ricardo, I suspect there are two back-ticks missing, right?

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>