Day 3: Maybe — Mini-Lists, or Mini-Exceptions

Maybe is like [] but “smaller” — Maybe t can store zero or one elements of type t, but not more.

There’s a category theory way of relating Maybe and []: natural transformations convert between Functors while also making sure that still fmap works.

Maybe and [] are both Functorss (because every Monad is also a Functor), and here are a couple of natural transformations between them from Data.Maybe. You might have seen them before:

maybeToList :: Maybe a -> [a]
listToMaybe :: [a] -> Maybe a

maybeToList gives a list containing Just the element, or an empty list for Nothing; and listToMaybe is a kind of “safe head” — you get Just the first element of the list, or Nothing if it is empty rather than a runtime error.

What it means above for fmap to work is that fmap and the natural transformation can be applied in either order and we end up with the same answer. For example, we can go from Maybe Int to [String] by using fmap show and maybeToList — we can follow either path on this diagram and we’ll get the same answer.

We can also test this law using QuickCheck.

First we’ll need some fairly arbitrary function that we can fmap:

func :: Integer -> Integer 
func = abs

and we can check going from lists to maybes:

> quickCheck (\l ->
      ((fmap func) . listToMaybe)  l
    == (listToMaybe . (fmap func)) l)
+++ OK, passed 100 tests.

and the other way round:

> quickCheck (\m ->
      ((fmap func) . maybeToList)  m
    == (maybeToList . (fmap func)) m)
+++ OK, passed 100 tests.

All we’ve looked at so far is Functor behaviour — we haven’t looked at laws for any of the monad operations.

Some natural transformations are monad morphisms, which satisfy a couple more laws: one is that return works the same before and after the morphism; the other is that bind works the same before and after the morphism.

Let’s QuickCheck those for maybeToList and listToMaybe.

return commutes with either of these transformations:

> quickCheck (\(x :: Integer) ->
  listToMaybe (return x) == return x)
+++ OK, passed 100 tests.
> quickCheck (\(x :: Integer) ->
  maybeToList (return x) == return x)
+++ OK, passed 100 tests.

It turns out, though, that although the bind vs morphism law does hold for maybeToList, it does not for listToMaybe:

checkMorph morph b = quickCheck $ \a ->
  (morph (do v <- a       ; b v)) 
 ==      (do v <- morph a ; morph (b v))

Let’s make actions that “filter out” values less than 5:

filterMaybe :: Integer -> Maybe Integer
filterMaybe v = if v >= 5 then Just v else Nothing
filterList :: Integer -> [Integer]
filterList v = if v >= 5 then [v] else []

so we can QuickCheck:

> checkMorph maybeToList filterMaybe
+++ OK, passed 100 tests.

But…

> checkMorph listToMaybe filterList
*** Failed! Falsifiable (after 7 tests and 4 shrinks):
[0,5]

QuickCheck has found an exception. Let’s work through it.

One way, we can run the computation in [] and convert to Maybe at the end:

[0,5] >>= filterList        -- = [5]
listToMaybe [5]             -- = Just 5

Or we can convert to Maybe at each step and bind those:

listToMaybe [0,5]             -- = Just 0
filterList 0                  -- []
listToMaybe (filterList 0)    -- Nothing

So if we stay in the [] monad as much as possible, we can explore all possible paths for answers, giving a list of answers, and do a “safe head” on that list at the end.

If we go to Maybe as soon as possible, we discard everything except the first choice as soon as possible — we only ever tried filterList on 0, rather than on both 0 and 5. Maybe is not rich enough to express all the things we can in [].

Going the other way, anything using Maybe only ever has at most one path to explore (and possibly none) — and [] is rich enough to express that.

So in that sense, Maybe is “smaller” than [], and that’s why I put “mini-lists” in the post title.

Maybe‘s flow is also exception-like.

We can run a step in a computation, and pass a single value onto the next steps.

Or we can abandon what we’re doing and not run those future steps at all. In exception language, that’s called throwing an exception. In Maybe language, that’s called Nothing.

If we treat Maybe as a mini-exception monad, can we make a monad morphism into a monad like IO that has real exceptions, in the same way we can go from Maybe-as-a-mini-list to real lists?

Perhaps, something like this:

maybeToIO :: Maybe a -> IO a
maybeToIO (Just x) = return x
maybeToIO Nothing = fail "Something went wrong"

This looks like it probably works but I haven’t tried proving all the laws.

If you treat something written in the Maybe monad as a “program”, you can imagine maybeToList and maybeToIO as two different “interpreters” that “run” that Maybe computation using an underlying monad ([] or IO). That’s not very interesting because Maybe is not very interesting. But Maybe we’ll come across more interesting examples later.

Other reading

Monads made difficult has lots of category theory stuff