Mike Vanier (mvanier) wrote,

Yet Another Monad Tutorial (part 5: error-handling monads)

In the previous article we showed how to derive and use the Maybe and list monads. In this article and the next we're going to look at how to use monads for error handling, also known as exception handling.

Error-handling computations

The kind of computation that we want to model with our error-handling monads will have types that are schematically like this:

  a --[possibly fail with a specified error condition]--> b

In words, this kind of computation maps an input value of type a to an output value of type b, but instead of returning a value of type b, it may fail with a specified error condition. This is clearly very similar to the Maybe monad. One difference is that all failures in the Maybe monad are indistinguishable (they return the Nothing value). In contrast, in error monads there are usually a variety of distinguishable error conditions that can cause a computation to fail. Another difference is that when running error handling computations it's desirable to have a mechanism for trapping errors and recovering from error situations in a controlled way (this goes by the name exception handling in most programming languages). As we'll see, using error monads you can easily roll your own exception handling system.

Error handling in Haskell

A programmer who wants to write code that may fail with specific error conditions has a large number of options in Haskell (maybe too large). Some of the more common ones include:

  • The error function
  • Exceptions in the IO monad
  • Extensible exceptions
  • Monadic exceptions

Let's look at these one at a time.

The error function

Most Haskell programmers are familiar with the error function. It is generally used just to abort a computation that cannot succeed. A good example is calling a factorial function with a negative integer:

  factorial :: Integer -> Integer
  factorial n | n < 0 = error "factorial: negative argument"
  factorial 0 = 1
  factorial n = n * factorial (n - 1)

The error function has a very interesting type:

  error :: String -> a

This means that the error function takes a String as argument and can "return" a value of any type whatsoever. In fact, of course, the error function doesn't return in the normal sense (that's the whole point: it's called to abort a computation). Therefore, what error's type really says is that its return type is of no consequence and can be whatever makes the type checker happy (in the factorial example, error's return type would thus be Integer).

Normally error is not used as an exception-handling mechanism. In other words, usually error is not used in situations where errors need to be recovered from. It's possible to catch errors thrown by error, but the recovery code has to be in the IO monad. I don't want to go into this any further (see the GHC documentation for more information), but I consider this to be a hack. Functional code should be functional, and that means not having weird behaviors that are not specified by the type signature. On the other hand, I understand why this approach was taken. Consider this version of the factorial function:

  factorial :: Integer -> Integer
  factorial 0 = 1
  factorial n = n * factorial (n - 1)

There's no ugly error call here, but if factorial is ever called with a negative input, the function will go into an infinite loop. If you restricted the second clause to just positive inputs:

  factorial :: Integer -> Integer
  factorial 0 = 1
  factorial n | n > 0 = n * factorial (n - 1)

then if factorial is called with a negative number, a pattern match error will occur which will also abort the computation and not result in an Integer being returned. The error function is a compromise to allow programmers to write functions which are total (i.e. have defined and terminating behaviors for all possible inputs) even when some of the inputs are invalid (i.e. the function is conceptually a partial function, like factorial).

We'll see a cleaner way to handle this below.

Error handling in the IO monad

The Haskell 98 standard specifies a way to deal with error conditions in the IO monad. There is a datatype called IOException (aliased to IOError), which can contain various kinds of error-related information, as well as the type of error condition. The number of error conditions is fixed (although there is a catch-all UserError category), so this isn't very sophisticated. Errors are raised in the IO monad using the ioError function and can be caught in the IO monad with the catch function. This approach is actually quite similar to what we will derive below, except that it runs inside the IO monad instead of inside a custom error-handling monad.

Extensible exceptions

A more general version of the Haskell 98 error handling system is found in the GHC module Control.Exception, which implements extensible exceptions in the IO monad. I don't want to get into the details here, but the main idea is that you can add your own exception types to the system as long as these types are instances of the Exception type class. This is an elegant system, except for the fact that these exceptions can once again only be caught in the IO monad.

Side note: There is a saying that the IO monad is the great "sin-bin" of the Haskell language, because so much functionality has been dumped into this monad which has nothing whatsoever to do with input or output. Using the IO monad for error handling is a good example of this. Haskell programmers are increasingly moving away from over-using the IO monad and towards a style where special-purpose monads are used to handle aspects of functionality that previously were dumped into the IO monad.

Monadic exceptions

The cleanest way to handle errors is to use a special-purpose error-handling monad, which is the topic of the rest of this article and the next.

The Either datatype

Recall the definition of the Maybe datatype:

  data Maybe a = Nothing | Just a

Maybe is a type constructor which maps a type (like Int) to a different type (like Maybe Int). Since Maybe only takes a single type argument, it is a unary type constructor. However, we don't want to use Maybe for a general-purpose error-handling system because we want to be able to represent information about errors that occur (if all errors result in a Nothing value, there can be no error-specific information). It turns out that we can get this with a slightly more complicated datatype called Either. It looks like this:

  data Either a b = Left a | Right b

Either, like Maybe, is a type constructor. However, unlike Maybe, it takes two type arguments, and is thus a binary type constructor. What Either allows you to do is to say of a data value "this data value can be one of these two types, but nothing else", and it can do this for any two types. For instance, let's consider the type Either String Int. A value of this type can be either Left s where s is a String, or Right i where i is an Int. Either has nothing fundamentally to do with error handling, but we will be able to use it to create an error handling system. In this case, the convention we will adopt is that the Left constructor will represent error values and the Right constructor will represent successful results of computations.

For instance, if we wanted a version of integer division that checks for divide-by-zero conditions, we might write something like this:

  safe_divide :: Int -> Int -> Either String Int
  safe_divide _ 0 = Left "divide by zero"
  safe_divide i j = Right (i `div` j)

Let's test it in ghci:

  ghci> 36 `safe_divide` 6
  Right 6
  ghci> 1 `safe_divide` 0
  Left "divide by zero"

The good news is that we have a clean way to say that a computation has failed, and we can give information about why it failed as well. The bad news is that this function is going to be tedious to use. For instance:

  -- f i j k = i + j / k
  f :: Int -> Int -> Int -> Either String Int
  f i j k = 
    case j `safe_divide` k of
      Left msg -> Left msg
      Right r -> Right (i + r)

This is pretty complicated considering what we are trying to do. In addition, the output type (Either String Int) is different from the input types (which are all Ints), so it's going to be hard to compose functions which return these Either values with functions that don't. But let's press on for now and deal with those problems later.

We can use the Either datatype to represent multiple kinds of error conditions. For instance, with integer division, we might want to fail if the two numbers are not evenly divisible as well as checking for division by zero. We can improve our safe_divide function accordingly:

  safe_divide :: Int -> Int -> Either String Int
  safe_divide _ 0 = Left "divide by zero"
  safe_divide i j | i `mod` j /= 0 = Left "not divisible"
  safe_divide i j = Right (i `div` j)

Now we have a division function for integers that can handle two error conditions. However, it's not easy to write code which detects which of the two conditions occurred. For instance, we might have situations where dividing two integers which are not evenly divisible is OK (we just throw away the remainder) but division by zero is probably never going to be OK. Let's try to write this using our safe_divide function:

  divide :: Int -> Int -> Either String Int
  divide i j = case i `safe_divide` j of
                 Left "divide by zero" -> Left "divide by zero"
                 Left "not divisible"  -> Right (i `div` j)
                 Right k               -> Right k

Do you see what the problem is here? We are actually pattern-matching on an error message! That was not supposed to be the purpose of error messages. Furthermore, if the error message was long and complicated, not only would it be tedious to re-type, but there is a good chance that we would make a typo which would show up as a run-time error, because this pattern match is not exhaustive (even though we know that these are the only errors that can occur). There has to be a better way. And there is! Let's define an algebraic datatype for our errors:

  data ArithmeticError =
      DivideByZero
    | NotDivisible
    -- could add more cases here
      deriving Show

The deriving Show part is just so that ArithmeticError values can be printed when testing the code in ghci. Now our definitions become:

  safe_divide :: Int -> Int -> Either ArithmeticError Int
  safe_divide _ 0 = Left DivideByZero
  safe_divide i j | i `mod` j /= 0 = Left NotDivisible
  safe_divide i j = Right (i `div` j)

  divide :: Int -> Int -> Either ArithmeticError Int
  divide i j = case i `safe_divide` j of
                 Left DivideByZero -> Left DivideByZero
                 Left NotDivisible -> Right (i `div` j)
                 Right k           -> Right k

Notice that the types of our functions are no longer Either String Int; because the error representation has changed to use ArithmeticErrors, the types are Either ArithmeticError Int. What's nice about the definition of divide is that if we forget one of the ArithmeticError cases, the compiler will let us know (assuming we've enabled exhaustive pattern match checking, which I always do).

One limitation is that if we decide later that we want to add another constructor to the ArithmeticError datatype, we will potentially need to modify a lot of code to handle the extra case. A more extensible approach (and the one used in GHC's Control.Exception module) is to use an existential type for error values. This is a fascinating topic, but it would lead us too far afield, so I'm going to stick to the simple algebraic datatype in what follows.

Let's recap. Our error-handling functions will return values which have the type Either e a, with a custom error type e as the datatype used in the Left constructor. This custom error type will itself be an algebraic datatype with one constructor for each class of errors. The arguments to the constructor (if any) will provide whatever information we want to attach to that class of errors. And with this, we can write clean functions that either succeed or result in specific errors.

What we haven't done is shown how to use these error-handling functions in a way which is not completely gross. Every time we call a function that may result in an error condition, we have to use a case statement to check for those error conditions. This is very reminiscent of the case in the C programming language where some functions return error codes which have to be analyzed before continuing in case an error occurred. Doing this is tedious in C, and it's just as tedious in Haskell. In other languages, this kind of problem led to the development of exception-handling systems. What's Haskell going to do about it? Hmmm, I wonder...

Making an error-handling monad

When we work with monads, we are working with monadic functions which have the general type a -> m b for arbitrary types a and b, and for a type constructor m. This type constructor must be a unary type constructor i.e. a "type function" which maps a type to a type. We saw this with the Maybe monad, where Maybe is a unary type constructor which maps a type (say, Int) to another type (Maybe Int). In this case, the type of the monadic functions will thus be a -> Maybe b.

All well and good, but how do we adapt this result to work with error-handling types? First of all, we have to figure out what the type of our monadic functions is going to be. It should come as no surprise that the basic error-handling function type is:

  a -> Either e b

for arbitrary types a and b, and for some error type e, which will typically be an algebraic data type like the ArithmeticError type shown above. Note that this is the error-handling counterpart to a non-error-handling function of type a -> b. Note also that via currying we can have error-handling functions with arbitrary numbers of arguments, for instance:

  a -> b -> Either e c

The safe_divide and divide functions above happen to have two input arguments (of type Int) and one output argument (of type Either ArithmeticError Int), so they are cases in point. Without loss of generality, we will only deal with one-argument functions of the form

  a -> Either e b

while realizing that through currying, our functions can actually have as many arguments as we want.

The problem now is that it might appear that the type

  a -> Either e b

is not in the shape of the standard monadic function type

  a -> m b

because this requires a unary type constructor m and what we have is the binary type constructor Either. But Haskell allows us to curry type constructor "applications" as well as function applications! In other words, we can rewrite the Either-containing type signature as:

  a -> (Either e) b

and Either e is a perfectly valid unary type constructor, since it is a partially-applied binary type constructor (applied here to some error type e). In the case of our ArithmeticError type, we can write

  a -> (Either ArithmeticError) b

and Either ArithmeticError is a unary type constructor: it takes as its "input" a type (b) and produces the type Either ArithmeticError b.

The reason that this is important is that it allows us to treat Either e (for any error type e) as a monad! Compare:

  a -> m b            -- general type of monadic functions
  a -> (Either e) b   -- type of monadic error-handling functions

So the monad m in the first case is just Either e for error-handling monads. In fact, of course, the parentheses can be omitted, so we write these types as just

  a -> Either e b

as you'd expect. Given all this, it shouldn't come as a surprise that the definition of the relevant monad would look like this:

  instance Monad (Either e) where
    (>>=)  = {- definition of >>= for error-handling monads -}
    return = {- definition of return for error-handling monads -}

As before, we will first derive the >>= operator based on what we want the monad to do for us, and then we'll derive the return function using the monad laws.

Deriving the >>= operator

In the context of our error-handling monad, the >>= operator will have the type:

  (Either e) a -> (a -> (Either e) b) -> (Either e) b

which we might as well write without superfluous parentheses as:

  Either e a -> (a -> Either e b) -> Either e b

The interpretation of this is similar to that of the Maybe monad. We are taking the result of an error-handling computation as our input. That input has the type Either e a, which means that it is "either" an error of type e or a non-erroneous value of type a. If it's an error, that error is just passed through unchanged. If it's not an error, the value of type a is extracted and passed to the function of type a -> Either e b, yielding the result of type Either e b. Writing the definition is very straightforward:

  (>>=) :: Either e a -> (a -> Either e b) -> Either e b
  Left err  >>= f  =  Left err
  Right val >>= f  =  f val

What this means in practice is that if you have a bunch of error-handling computations being carried out one after another, and an error happens in one of them, all the computations subsequent to that error (represented by the monadic function f, which may be made up of a bunch of other monadic functions composed together) are not carried out; instead, the error value is the return value of the entire computation.

Although this definition is plausible, we still have to verify that it doesn't violate the monad laws. Before we do that, we have to define what return means in this monad.

Deriving the return function

The type of the return function in this monad is:

  return :: a -> Either e a

Recall that the type Either e a is:

  data Either e a = Left e | Right a

It wouldn't make much sense to return a Left value from return; for one thing, no error has occurred, and even if it had, which error would we use? So it's plausible that return will return a Right ??? value for some ???. We need to fill in this definition:

  return :: a -> Either e a
  return x = Right ???

Since we know nothing whatsoever about the value x other than that it has the type a, the simplest thing we can put on the right-hand side is just x. This also makes sense given that we know that return is the monadic equivalent of the identity function. So this definition is plausible:

  return :: a -> Either e a
  return x = Right x

Again, we need to check that this doesn't violate the monad laws.

The monad laws

The first monad law, written in terms of return and >>=, is:

  return x >>= f  ==  f x

Using our definitions for the Either e monad, we have:

  return x >>= f
    = Right x >>= f  -- definition of return
    = f x            -- definition of >>=
    -- Q.E.D.

Check. The second monad law is:

  mv >>= return  ==  mv

Let's see if this works:

  -- Case 1: mv == Left err
  mv >>= return
    = Left err >>= return      -- definition of mv
    = Left err                 -- definition of >>=
    = mv                       -- definition of mv
  -- Case 2: mv == Right val
  mv >>= return
    = Right val >>= return     -- definition of mv
    = return val               -- definition of >>=
    = Right val                -- definition of return
    = mv                       -- definition of mv
  -- Both cases correct, so Q.E.D.

Yup. That was pretty easy. Now let's attempt the somewhat harder task of proving monad law 3 correct. The third law is:

  (mv >>= f) >>= g  ==  mv >>= (\x -> (f x >>= g))

And so then:

  -- Case 1: mv == Left err
  -- Left-hand side:
  (mv >>= f) >>= g
    = (Left err >>= f) >>= g               -- definition of mv
    = Left err >>= g                       -- definition of >>=
    = Left err                             -- definition of >>=
  -- Right-hand side:
  mv >>= (\x -> (f x >>= g))
    = Left err >>= (\x -> (f x >>= g))     -- definition of mv
    = Left err                             -- definition of >>=
  -- Case 1 checks out.

  -- Case 2: mv == Right val
  -- Left-hand side:
  (mv >>= f) >>= g
    = (Right val >>= f) >>= g              -- definition of mv
    = (f val) >>= g                        -- definition of >>=
    = f val >>= g                          -- remove unnecessary parentheses
  -- Right-hand side:
  mv >>= (\x -> (f x >>= g))
    = Right val >>= (\x -> (f x >>= g))    -- definition of mv
    = (\x -> (f x >>= g)) val              -- definition of >>=
    = (f val >>= g)                        -- function application (beta reduction)
    = f val >>= g                          -- remove unnecessary parentheses
  -- Case 2 checks out, so Q.E.D.

And we're done. Either e is indeed a monad. The complete definition of the monad is thus:

   instance Monad (Either e) where
     return x = Right x   -- or just: return = Right

     (Left x)  >>= f = Left x
     (Right x) >>= f = f x

Notice that the specific error type e is irrelevant. This means that Either e is a monad regardless of what error type e is used. So Either ArithmeticError is a monad, Either String is a monad, and Either [any other type] is a monad too. (Generic code like this gives Haskell programmers a warm fuzzy feeling.) Of course, as we saw above, the error type does matter, but not for the monad-ness (monadnicity?) of the computation.

Also notice that if we wanted to, we could write the definition of >>= in a slightly different (but equivalent) way:

    xx >>= f =
      case xx of
        Left x  -> Left x
        Right x -> f x

All we've done here is replace two equations with an explicit case statement, which is something that Haskell compilers do for us when compiling code. This way of writing the >>= operator will help you solve an exercise I give below.

Now that we've established that, it's time to see it in action (pun intended!).

Example: using the Either e monad in a computation

Consider this very simple function on integers:

  -- f i j k = i / k + j / k
  f :: Int -> Int -> Int -> Int
  f i j k = (i `div` k) + (j `div` k)

We use div instead of the / operator because / is not defined for integers in Haskell. This function will fail if k is 0. In addition, if we want to have it fail when either i or j are not evenly divisible by k, we're out of luck; because of the way div works, it will just throw away the remainders.

Let's try it out:

  ghci> f 6 4 2
  5
  ghci> f 6 4 0
  *** Exception: divide by zero
  ghci> f 6 3 2
  4

f 6 4 2 is a nice case where both of the first two arguments are divisible by the third, giving the expected result 5. When the third argument is 0 we get an exception, and when the second argument is not divisible by the third, the remainder is thrown away.

Before I show you the monadic version of this, I want to rewrite the function f slightly:

  -- f' i j k = i / k + j / k
  f' :: Int -> Int -> Int -> Int
  f' i j k = 
    let q1 = i `div` k
        q2 = j `div` k
    in q1 + q2

What we're doing here is giving names to all the subexpressions, so that only one arithmetic expression is computed on a line. This may look different from the previous example, but after it passes through GHC's optimization passes, both forms reduce to the exact same code. You'll see why I did this shortly.

Now let's write this code using an Either ArithmeticError Int return type, but without using the monadic machinery. We get this:

  -- g i j k = i / k + j / k
  g :: Int -> Int -> Int -> Either ArithmeticError Int
  g i j k = 
    case i `safe_divide` k of
      Left  err1 -> Left err1
      Right q1   -> 
        case j `safe_divide` k of
          Left  err2 -> Left err2
          Right q2   -> Right (q1 + q2)

This is kind of gross, but we'll let that pass for now. Let's test it:

  ghci> g 6 4 2
  Right 5
  ghci> g 6 4 0
  Left DivideByZero
  ghci> g 6 3 2
  Left NotDivisible

This is nice in the sense that whenever there is an error (as we have defined it) we get a specific error result. Now let's rewrite this using the Either e monad:

  -- g' i j k = i / k + j / k
  g' :: Int -> Int -> Int -> Either ArithmeticError Int
  g' i j k = 
    do q1 <- i `safe_divide` k
       q2 <- j `safe_divide` k
       return (q1 + q2)

This gives the exact same results as the previous version:

  ghci> g' 6 4 2
  Right 5
  ghci> g' 6 4 0
  Left DivideByZero
  ghci> g' 6 3 2
  Left NotDivisible

However, the function g' is much simpler and clearer than g because it doesn't have to explicitly handle any of the error cases. When an error case occurs, it is returned as the result of the function, but if not, the correct result of a subexpression is bound to a name (q1 or q2), and that result can be used in later parts of the computation. So what monads buy us here is exactly what they buy us for the Maybe monad: the code is a lot simpler to write. The more complicated the error-handling function, the more important this will be.

Note that, as always, we can rewrite this without using the do-notation as follows:

  -- g'' i j k = i / k + j / k
  g'' :: Int -> Int -> Int -> Either ArithmeticError Int
  g'' i j k = 
    i `safe_divide` k >>= \q1 -> 
      j `safe_divide` k >>= \q2 ->
        return (q1 + q2)

This is identical to the function g'. We rarely do this in practice (except for very short functions) because the do form is usually more readable, but it would be a really good exercise at this point to make sure that you understand the desugaring of the do form into the form with explicit >>= operators.

NOTE: There are situations in which the translation from the do-notation into the version with explicit >>= operators is a bit more complicated than what I've described. If the left-hand side of the -> is a single name, it's valid, but if it's something more complicated, a pattern-match failure can result, which will result in the fail function of the monad being called. We will talk about this at length in the next article, because there will be a connection between this and certain error-handling type classes that we will be discussing.

Once you've done that, you should then take the definition of g'' and reduce it to the function g using the definitions of >>= and return for the Either e monad. (See the hint above.)

The last lines in g' and g'' contain an explicit return. However, you can put returns anywhere, since all they do is lift regular values into the Either e monad. For instance, we could define a function gg as follows:

  gg :: Int -> Int -> Int -> Either ArithmeticError Int
  gg i j k = 
    do q1 <- i `safe_divide` k
       x1 <- return (q1 * 2 - i)
       q2 <- j `safe_divide` k
       x2 <- return (q2 * 3 + j)
       return (q1 * x1 + q2 * x2)

What this does isn't important, but it does show that you can put returns in the interior of a monadic function. Lines of the form:

       x <- return y

are converting y to a monadic value and then unpacking that value into x. Thus x and y must have the same type. I emphasize again that return in Haskell has nothing whatsoever to do with returning from a function! Make sure you understand this before you continue.

The last thing I want to do in this section is to contrast three functions: f, f', and g':

  f :: Int -> Int -> Int -> Int
  f i j k = (i `div` k) + (j `div` k)

  f' :: Int -> Int -> Int -> Int
  f' i j k = 
    let q1 = i `div` k
        q2 = j `div` k
    in q1 + q2

  g' :: Int -> Int -> Int -> Either ArithmeticError Int
  g' i j k = 
    do q1 <- i `safe_divide` k
       q2 <- j `safe_divide` k
       return (q1 + q2)

As you can see, the monadic function g' is structurally very similar to the non-monadic function f'. Unlike f or f', though, g' will catch division-by-zero errors and not-divisible errors and report them in a usable form. The monadic machinery has made it possible to turn grungy error-handling functions like g into error-handling functions no grungier than (non error-handling) functions like f'. You might wonder if you can go further than this and write monadic functions like g' in a form like the non-monadic function f, i.e. something like:

  -- not valid Haskell!
  g''' :: Int -> Int -> Int -> Either ArithmeticError Int
  g''' i j k = (i `safe_divide` k) + (j `safe_divide` k)

The answer is: no, you can't. The reason is that, in a monad, you are enforcing a certain order of operations: the expression i `safe_divide` k will be evaluated before the expression j `safe_divide` k. This is necessary in order to let us abort the computation early if the first expression results in an error. On the other hand, for normal Haskell expressions like (i `div` k) + (j `div` k) the order of operations is not specified; Haskell is a lazy language and can evaluate this expression in whatever order it wants. So, unfortunately, we can't make our monadic computation look just as simple as the corresponding non-monadic one, but we can come pretty close.

NOTE: Some monadic computations care more about sequencing than others. For any computation in the IO monad and most computations in state monads (to be discussed later), sequencing is absolutely essential (for instance, if you print two strings one after the other, you want them to come out in the order you specified, not in some other order!). For some computations in other monads, sequencing is less important. In the present case, whether i `safe_divide` k or j `safe_divide` k is evaluated first is not that important; the error handling is the same for both functions and whether one expression or the other fails first is irrelevant. Nevertheless, whether we like it or not, monads impose the sequencing of operations on their computations and we have to be explicit about this when writing monadic code.

So far, we've used the Either e monad and the ArithmeticError datatype to achieve two things:

  1. writing an error-handling function which gives specific errors for all the error conditions we care about;

  2. writing these functions in a clean way that doesn't involve lots of ugly nested case statements and redundant boilerplate code.

What we haven't done yet is to create a system in which errors can be recovered from in a selective manner. This is what other languages offer in their exception handling systems. As we will see next time, in Haskell it's incredibly easy to define your own exception handling system in a way which builds upon what we've just done.

Next time

In the next installment we'll finish our discussion of error-handling monads by talking about the MonadError and Error type classes, two type classes that will enable us to use the monadic machinery we've already developed to do exception handling (error recovery) in a reasonable way.

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded  

  • 0 comments