Maybe Monad...

Over the next several weeks, we will study several type classes which play a central role in Haskell programming; they describe really common and powerful patterns of computation.

To work up to this, let’s do a bit of programming. Recall the definition of the Maybe type, which can be used in many cases to encode either “failure” or a “successful” result. We will see examples of:

1. mapping Maybe values,
2. applying Maybe functions to Maybe arguments, and
3. sequencing Maybe “actions.”

After studying this progression of programming patterns involving Maybe, maybe Monad… will not seem so scary.

Mapping Maybe Values

Let’s write a couple routine recursive definitions that “map over” Maybe values.

maybeAddOne :: Num a => Maybe a -> Maybe a
maybeAddOne Nothing  = Nothing
maybeAddOne (Just n) = Just $ 1 + n

maybeSquare :: Num a => Maybe a -> Maybe a
maybeSquare Nothing  = Nothing
maybeSquare (Just n) = Just $ n * n

maybeLength :: Maybe [a] -> Maybe Int
maybeLength Nothing   = Nothing
maybeLength (Just xs) = Just $ length xs

maybeShow :: Show a => Maybe a -> Maybe String
maybeShow Nothing  = Nothing
maybeShow (Just x) = Just $ show x

As usual when seeing repeated structure in our code, we look for ways to streamline, in this case by factoring out the mapping function.

mapMaybe :: (a -> b) -> Maybe a -> Maybe b
mapMaybe f Nothing  = Nothing
mapMaybe f (Just x) = Just $ f x

maybeAddOne = mapMaybe (1+)
maybeSquare = mapMaybe (^2)
maybeShow   = mapMaybe show

The type and expression structure of mapMaybe should look familiar. Recall our old friend map that “maps over” lists.

map :: (a -> b) -> [a] -> [b]
map f []     = []
map f (x:xs) = f x : map f xs

Very many types arise in programming where having this kind of general map function is useful. So, treating them uniformly in the language will reap benefits. Stay tuned.

Applying Maybe Functions

mapMaybe works well for functions with one argument…

mapMaybe (+2) (Just 10)           -- Num a => Maybe a

… but doesn’t help with more:

mapMaybe (+) (Just 10)            -- Num a => Maybe (a -> a)
mapMaybe (+) (Just 10) (Just 2)   -- type error

We also want to apply Maybe functions.

applyMaybe                    :: Maybe (a -> b) -> Maybe a -> Maybe b
applyMaybe (Just f) (Just x)  =  Just $ f x
applyMaybe _        _         =  Nothing

Now we can handle multi-arg Maybe functions:

>           (+) `mapMaybe`   Just 10 `applyMaybe` Just 2
>           (+) `mapMaybe`   Nothing `applyMaybe` Just 2

Alternatively, we could define

pureMaybe :: a -> Maybe a
pureMaybe = Just

and then use only applyMaybes (no initial mapMaybe):

> pureMaybe (+) `applyMaybe` Just 10                       -- Num a => Maybe (a -> a)
> pureMaybe (+) `applyMaybe` Just 10 `applyMaybe` Just 2   -- Num a => Maybe a
> pureMaybe (+) `applyMaybe` Nothing `applyMaybe` Just 2
> Nothing       `applyMaybe` Nothing `applyMaybe` Just 2

Lifting Pure Functions

We can write helper functions to “lift” the application of functions with different arities. For example:

lift3Maybe :: (a -> b -> c -> d) -> Maybe a -> Maybe b -> Maybe c -> Maybe d
lift3Maybe f ma mb mc =
  pureMaybe f `applyMaybe` ma `applyMaybe` mb `applyMaybe` mc

It is a common pattern to apply a function of arity n to n Maybe arguments. This will arise for very many other types, too. Stay tuned.

mapMaybe   :: {- forall t1, t2. -} (t1 -> t2) -> Maybe t1 -> Maybe t2
mapMaybe f :: Maybe a -> Maybe (b -> c -> d)

lift3Maybe f ma mb mc =
  f `mapMaybe` ma `applyMaybe` mb `applyMaybe` mc

Sequencing Maybe Actions

Motivating example:

type Person = String

parent :: Person -> Maybe Person
parent =
  undefined
  -- assume this "database" is defined in some reasonable way:
  -- as a function, or using an association list, or some
  -- efficient "lookup table" data structure

grandparent :: Person -> Maybe Person
grandparent p =
  case parent p of
    Nothing -> Nothing
    Just pp ->
      case parent  of
        Nothing  -> Nothing
        Just ppp -> Just ppp

Can avoid the second case expression…

grandparent :: Person -> Maybe Person
grandparent p =
  case parent p of
    Nothing -> Nothing
    Just pp -> parent pp

but still, it is tedious to manipulate Nothing and Just values explicitly. However, neither mapMaybe nor applyMaybe can help here; the second function call, parent, returns Nothing or Just some value depending on the value of parent p.

We might start by defining something like applyMaybe but where the (Maybe) function Maybe returns a result:

applyMaybe' :: Maybe (a -> Maybe b) -> Maybe a -> Maybe b
applyMaybe' (Just f) (Just a) = f a
applyMaybe' _        _        = Nothing

This is fine, but actually does more work and is more restrictive than needed; it’s redoing part of what applyMaybe does. Instead:

applyActionMaybe :: (a -> Maybe b) -> Maybe a -> Maybe b
applyActionMaybe _ Nothing  = Nothing
applyActionMaybe f (Just x) = f x

If we squint a little, we might think of the first argument as a function from a to b, but which may “fail” (i.e. by returning Nothing). This is an “effectful” function (an “action”), which may have the effect of failing when run.

Now we can avoid manipulating Nothing explicitly:

grandparent p =
  parent `applyActionMaybe` (parent `applyActionMaybe` (Just p))

If we flip the arguments to applyActionMaybe

andThenMaybe :: Maybe a -> (a -> Maybe b) -> Maybe b
andThenMaybe = flip applyActionMaybe

then it looks more like sequencing the function calls (“actions”) one after another from left-to-right:

grandparent p =
  parent p `andThenMaybe` (\pp ->
    parent pp `andThenMaybe` (\ppp ->
      Just ppp
  ))

Or, almost like straight-line code:

grandparent p =
  parent p  `andThenMaybe` \pp ->
  parent pp `andThenMaybe` \ppp ->
  pureMaybe ppp

Errors Within a Sequence of Actions

sibling :: Person -> Person -> Bool
sibling x y =
  case (parent x, parent y) of
    (Just px, Just py) -> px == py && x /= y
    _                  -> False

There are a couple aspects that are undesirable. The first is that we should perform the x /= y comparison before forcing either parent x or parent y to evaluate.

sibling x y =
  x /= y && sameParent where
    sameParent =
      case (parent x, parent y) of
        (Just px, Just py) -> px == py
        _                  -> False

The other is that we have to manually pattern match to get to the interesting, non-error case. If we encode Bools using Maybe

guardMaybe :: Bool -> Maybe ()
guardMaybe True  = Just ()
guardMaybe False = Nothing

then we can reuse the Maybe sequencing:

sibling :: Person -> Person -> Maybe ()
sibling x y =
  (guardMaybe $ x /= y) `andThenMaybe` \() ->
  parent x              `andThenMaybe` \px ->
  parent y              `andThenMaybe` \py ->
  guardMaybe $ px == py

Notice that we changed the type of sibling, but it’s trivial to convert from Maybe () back to Bool.

Lots of other types of values will have notions of sequencing actions. Stay tuned.

Infix Operators

Applicative Style

It is a common pattern to apply a function of arity n to n Maybe arguments. To make this common case look as close to function application as possible, we can define two helper infix operators.

(<$>) = mapMaybe        -- resembles ($) for normal function application
(<*>) = applyMaybe

Now, the arity-n pattern above can be written in applicative style:

lift2Maybe f ma mb =
  f <$> ma <*> mb

lift3Maybe f ma mb mc =
  f <$> ma <*> mb <*> mc

lift4Maybe f ma mb mc md =
  f <$> ma <*> mb <*> mc <*> md

For example, the following are equivalent:

> (+) <$> Just 1 <*> Just 2
> pure (+) <*> Just 1 <*> Just 2
> lift2Maybe (+) (Just 1) (Just 2)

Sequencing Actions

By defining an infix operator for andThenMaybe

(>>=) = andThenMaybe

we can write sequences of Maybe actions as:

grandparent p =
  parent p  >>= \pp ->
  parent pp >>= \ppp ->
  pureMaybe ppp

sibling x y =
  (guardMaybe $ x /= y) >>= \() ->
  parent x              >>= \px ->
  parent y              >>= \py ->
  guardMaybe $ px == py

Composing Actions

Recall the last version of grandparent above. We can eta-reduce the innermost lambda:

grandparent p =
  parent p `andThenMaybe` (\pp -> parent pp `andThenMaybe` pureMaybe)

And, based on the definition of andThenMaybe:

grandparent p =
  parent p `andThenMaybe` parent

This pattern of function composition can be abstracted:

(<=<) :: (b -> Maybe c) -> (a -> Maybe b) -> (a -> Maybe c)
(f <=< g) x = g x `andThenMaybe` f

And now:

grandparent = parent <=< parent

Recap: A Monad Roadmap

We’ve seen a bunch of useful functions for manipulating Maybe values.

mapMaybe           ::        (a ->       b) -> (Maybe a -> Maybe b)
applyMaybe         ::  Maybe (a ->       b) -> (Maybe a -> Maybe b)
flip andThenMaybe  ::        (a -> Maybe b) -> (Maybe a -> Maybe b)

pureMaybe          ::  a -> Maybe a
guardMaybe         ::  Bool -> Maybe ()

For each of the above, we can replace Maybe with many other different types t and implement suitable definitions with analogous type signatures and behavior — resulting in the “big three” type classes in the Haskell FAMily (Functor, Applicative, Monad):

fmap          ::  Functor       =>    (a ->   b) -> (t a -> t b)
apply         ::  Applicative_  =>  t (a ->   b) -> (t a -> t b)
flip andThen  ::  Monad_        =>    (a -> t b) -> (t a -> t b)

pure          ::  Applicative_  =>  a -> t a
guard         ::  Alternative_  =>  Bool -> t ()

-- Infix Notation ------------------------------------------------

(<$>) = map      ::  Functor       =>  (a -> b) -> (t a -> t b)
(<*>) = apply    ::  Applicative_  =>  t (a -> b) -> (t a -> t b)
(>>=) = andThen  ::  Monad_        =>  t a -> (a -> t b) -> t b

These constraints preview type classes that will house each pattern of computation. In the next several sections, we’ll study these — and other — common patterns of computation. You may find it useful to refer back to this roadmap from time to time.

Exercises

Exercise 1. Implement the following function in terms of map and mapMaybe:

mapListMaybe :: (a -> b) -> [Maybe a] -> [Maybe b]

Exercise 2. Implement the following function in terms of map and mapMaybe:

mapMaybeList :: (a -> b) -> Maybe [a] -> Maybe [b]

Exercise 3. Implement the following function in terms of andThenMaybe; you may not use pattern matching directly:

joinMaybe :: Maybe (Maybe a) -> Maybe a

Exercise 4. Re-implement the following function directly (using pattern matching, not using andThenMaybe):

joinMaybe :: Maybe (Maybe a) -> Maybe a

And then implement andThenMaybe in terms of joinMaybe and other *Maybe functions (you may not use pattern matching directly).

Source Files

• MaybeMonad.hs