Monads - What are they good for?

In an attempt to brush up on my crypto understanding, I’ve decided to attempt the Matasano Crypto Challenges, aka the Cryptopals challenges. (Github repo) And since I want this to be a learning opportunity, I’m doubling down by choosing to implement all my solutions in language and paradigm that was unfamiliar with me, so that even if I saw a problem I was already familiar with, I would be forced to view it differently. I chose Haskell and Rust as my weapon of choice, since for all the buzz they seem to get (Haskell especially), I don’t really know that much about them.

(A note: while this post is about my experience learning Haskell, it is not a haskell tutorial. Some amount of familiarity with functional programming is assumed, but not much, since I’m still picking it up myself.)

I do think that functional languages like Haskell have a lot of useful features that are underemphasized in traditional education. One of my solutions to the Google Foobar Challenge was a memoized recursive function. It was giving me correct answers, but it wasn’t efficient enough to run within the time limit. I wanted to know the time complexity of the algorithm, but during the entire semester of my Algorithms class, we had not once touched on measuring the complexity of a function like this, while we’d spent a whole week on loop invariants. I had to puzzle it out by considering which subcases would actually be computed (not all of them, so translating this to a dynamic programming algorithm would be even less efficient.)

But has using Haskell saved me time? I don’t know. I considered measuring how long it took me to solve these problems versus solving similar imperative problems, but such measurements wouldn’t have accounted for the time it took me to learn the language as I went (you could say that my task of learning Haskell was being evaluated lazily.) I do know that in most cases, once I got the program to compile, it was correct for all inputs. But I also know that I had a lot more compile errors that took me a good amount of time to understand. From a design perspective, this was probably a good thing. Making it impossible to express bad code increases the quality of the code you create. But did it save me time? I don’t have the numbers, but I don’t think it did.

I also learned that there’s a difference between writing code in Haskell and actually understanding what Haskell can do. I wrote my initial solutions to the first couple problems with no understanding of monads, one of Haskell’s most useful features. And these solutions worked. But they wordy and had an awful lot of boxing/unboxing of Maybe values.

For example, here was my initial implementation of a function that converted a hex string into a list of bytes:

hexChars = "0123456789ABCDEF"

{- Converts a hex string into a byte array -}
hexToBytes :: String -> [Word8]
hexToBytes hexes = hexToBytes' (map toUpper hexes) 0

hexToBytes' (char1 : char2 : xs) pos = case (maybeByte1, maybeByte2) of
    (Nothing, _) -> error ("Bad input at position " ++ show pos)
    (_, Nothing) -> error ("Bad input at position " ++ show (pos+1))
    ((Just byte1), (Just byte2)) -> fromIntegral(byte1*16 + byte2) :: Word8 : hexToBytes' xs (pos + 2)
    where maybeByte1 = char1 `elemIndex` hexChars
          maybeByte2 = char2 `elemIndex` hexChars
hexToBytes' (char1 : []) pos = error "Input of odd length"
hexToBytes' [] pos = []

The idea behind the function was simple. Define it recursively, so that we take each pair of characters in the input and convert them to their byte values. But the expression of this wasn’t simple. The elemIndex function doesn’t return an value of type Int, it returns an value of type Maybe Int, which could contain an Int, or could contain Nothing. This is Haskell’s approach to operations that may not return a meaningful answer. Instead of returning an error code or throwing an exception, it returns a Maybe. This means that the possibility of the function not returning successfully is baked into the function’s signature. Extracting the value inside the Maybe requires several lines of pattern matching.

Maybe this is desired. It allows us to return helpful error messages on bad input. But since Haskell is evaluated lazily, there’s no way of predicting when these errors are going to be thrown. We can’t get a stack trace, so knowing that somewhere we’re calling hexToBytes with bad input isn’t necessarily that helpful for debugging. An error message that’s meaningless at the high level is only marginally better than no error message at all.

I could have avoided repeating the error message specification by including another function in the where block that pattern matched the Maybe and extracted it, but I would have had to pass the position into the function, where it really didn’t belong. The issue was that I wanted a meaningful error message that could only be generated at a lower level that didn’t have any understanding of the larger program in context. And I was bypassing the Maybe type to do it. I was actively wrestling with the language instead of trying to leverage its features. (Sure enough, I learned that using error in this context is discouraged.) Surely there was a more “Haskallian way to do it.”

This is where I learned about Monads, the bread and butter of Haskell

I first tried to learn Haskell by reading Learn You a Haskell For Great Good, which explained monads mostly in terms of the type signatures of their functions, which led me to see them as some sort of esoteric element of category theory. A few examples wasn’t enough for me to grasp why monads mattered, or why I would want to use them. It wasn’t until I read Real World Haskell that I understood how to think of monads in a way that could improve even simple code: monads represented a context in which an operation can take place, and they alleviate the need to give this context special consideration. Maybe, as a monad, represents a context where we expect a value, but it may not be there. List, as a monad, represents a context where we expect a value but may find an arbitrary number of values. Code that does not abstract this away would have to pattern match against every Maybe it comes across in order to access the inner value, manually handling every case where the Maybe is a Nothing. But functions on Monads allow the function to be oblivious to the context of the value, and allow passing the values within the monads to functions that are also unaware of the context. The possibility of a value being Nothing becomes someplace else’s problem, allowing functions to focus on their single responsibility. This is a powerful tool for terse readable code. Whereas before my function was cluttered with Nothing checks (not as cluttered as it could have been, certainly. If I wanted to demonstrate the ills of manually matching each Maybe, I could have come up with a much worse example). But now the function is cleaner, and its behavior is more obvious.

Instead of extracting a value from a Maybe as soon as I get it, I can keep the entire computation within the Maybe context, only extracting the value at the end. There’s no performance penalty, because if the initial elemIndex returns Nothing, lazy evaluation ensures that this Nothing propagates through the rest of the function without performing any unnecessary computations.

This was my final version of the same function, using Haskell’s do-syntax.

hexToBytes hexes = hexToBytes' (map toUpper hexes)
hexToBytes' (char1 : char2 : xs) = do
    tail <- hexToBytes' xs
    byte1 <- char1 `elemIndex` hexChars
    byte2 <- char2 `elemIndex` hexChars
    return ((fromIntegral(byte1*16 + byte2) :: Word8) : tail)
hexToBytes' [_] = Nothing
hexToBytes' [] = Just []

The do-block is actually syntactical sugar for binding a binding a bunch of monads together so that each one is built by applying a function to the result of the previous one. If we desugar this code block, we can see the nested functions that make up the final monad:

hexToBytes hexes = hexToBytes' (map toUpper hexes)
hexToBytes' (char1 : char2 : xs) =
    hexToBytes' xs >>= \tail ->
        char1 `elemIndex` hexChars >>= \byte1 ->
            char2 `elemIndex` hexChars >>= \byte2 ->
                return ((fromIntegral(byte1*16 + byte2) :: Word8) : tail)
hexToBytes' [_] = Nothing
hexToBytes' [] = Just []

This is still readable, but it’s easy to see how a more complicated function could get messy quickly, especially with the extra indentation that do-notation makes unnecessary.

Now, do we lose the ability to include a useful error message? Maybe. But keep in mind that the error message wasn’t that useful to begin with. The only value was that it gave us the position in the hex string that was invalid, which isn’t hard to figure out. But because haskell uses lazy evaluation, we wouldn’t even know which hex string it was! If we really need to display that information, there are other better ways to do it in Haskell. (The Either type as a monad can hold a result or an error message.) But in this case, we don’t need that. We can keep it simple. And this new code is a lot simpler, and a lot more readable. It does change our type signature (we now return Nothing on invalid input instead of throwing an error), but you know what? The new behavior makes sense. Nothing is for computations that may fail, and this computation can only fail in one way. If hexToBytes returns nothing, the fix is clear: Check you input! And if we use monads, we can detect and handle errors where we need to without having to resort to thrown exceptions.