Maybe via Cont

The essence of the Maybe monad was that we have a computation we can abort at any time by returning Nothing. The result of the whole computation is then also Nothing. This is captured in the following equivalent of the Maybe monad:

type MaybeC r a = Cont (Maybe r) a

runAbortable :: MaybeC r r -> Maybe r
runAbortable f = runCont f Just

You may wonder why Maybe r is part of the definition of MaybeC. Didn't we want to make this all work without Maybe? Not exactly. We only said that we didn't want to make Maybe itself a monad. We want to use Cont to simulate the behaviour of the Maybe monad.

The MaybeC values corresponding to Nothing and Just x are

nothing :: MaybeC r a
nothing = Cont (\_ -> Nothing)

just :: a -> MaybeC r a
just x = Cont (\cc -> cc x)

Together with the (>>=) operator of the Cont monad (!), these two values achieve exactly the same behaviour as plain old Nothing and Just together with the (>>=) operator of the Maybe monad. In particular, just x >>= f applies f to x, and nothing >>= f just produces Nothing without evaluating f.

Let's try it out. Here is how we implemented inverses using the Maybe monad:

inverses :: [Double] -> Maybe [Double]
inverses = mapM invert
  where
    invert 0 = Nothing
    invert x = Just (1 / x)

GHCi

>>> :{
  | inverses = mapM invert
  |   where
  |     invert 0 = Nothing
  |     invert x = Just (1 / x)
  | :}
>>> inverses [1,2,3,4,5]
Just [1.0,0.5,0.3333333333333333,0.25,0.2]
>>> inverses [1,3,0,4,5]
Nothing

Using the MaybeC monad, we have

inverses :: [Double] -> Maybe [Double]
inverses xs = runAbortable (mapM invert xs)
  where
    invert 0 = nothing
    invert x = just (1 / x)

GHCi

>>> :{
  | type MaybeC r a = Cont (Maybe r) a
  |
  | runAbortable :: MaybeC r r -> Maybe r
  | runAbortable f = runCont f Just
  | :}
>>> :{
  | nothing :: MaybeC r a
  | nothing = cont (\_ -> Nothing)
  |
  | just :: a -> MaybeC r a
  | just x = cont (\cc -> cc x)
  | :}
>>> :{
  | inverses :: [Double] -> Maybe [Double]
  | inverses xs = runAbortable (mapM invert xs)
  |   where
  |     invert 0 = nothing
  |     invert x = just (1 / x)
  | :}
>>> inverses [1,2,3,4,5]
Just [1.0,0.5,0.3333333333333333,0.25,0.2]
>>> inverses [1,2,0,4,5]
Nothing

(Note the use of cont instead of Cont in the definitions of nothing and just. That's because in the standard library, Cont r = ContT r Identity, that is, there is no Cont type constructor. The standard library offers the function cont though, which has the type cont :: ((a -> r) -> r) -> Cont r a.)

So how does this work? If the definitions of nothing and just do what we want, then we should have

nothing >>= f = nothing
just x  >>= f = f x

Let's see whether that's true. To do this, we need to remember that

x >>= f = Cont $ \c -> runCont x (\a -> runCont (f a) c)

This gives

nothing >>= f
    = Cont $ \c -> runCont nothing (\a -> runCont (f a) c)    -- Definition of (>>=)
    = Cont $ \c -> (\_ -> Nothing) (\a -> runCont (f a) c)    -- Definition of nothing
    = Cont $ \c -> Nothing                                    -- Function application
    = nothing                                                 -- Definition of nothing

and

just x >>= f
    = Cont $ \c -> runCont (just x) (\a -> runCont (f a) c)    -- Definition of (>>=)
    = Cont $ \c -> (\cc -> cc x) (\a -> runCont (f a) c)       -- Definition of just
    = Cont $ \c -> (\a -> runCont (f a) c) x                   -- Function application
    = Cont $ \c -> runCont (f x) c                             -- Function application
    = Cont $ runCont (f x)                                     -- eta-Reduction
    = f x                                                      -- Cont . runCont = id

We have ourselves a Maybe monad built entirely from Cont.