Learn Haskell Part 6: Express sequence of actions with Monads

Choice from past context

The problem with ifThenElseA

There is a problem with Applicative. It returns weird results when using this abstraction to make decisions. We implemented before a function called ifThenElse:

ifThenElse p y n = if p then y else n

We applied this function to values wrapped in the Maybe Functor using <*> (merge) operator, but did not see really how it worked when a Nothing is given. Let's try:

λ> ifThenElseA p y n = fmap ifThenElse p <*> y <*> n
λ> ifThenElseA Nothing (Just 1) (Just 2)
Nothing

For now, nothing really surprising, if we cannot even test the predicate, well, we cannot chose a value. Let's try something else:

λ> ifThenElseA (Just True) Nothing (Just 2)
Nothing

Ok, still understandable, if we chose the y value, since it's Nothing, we get Nothing. Let's continue:

λ> ifThenElseA (Just True) (Just 1) Nothing
Nothing

Now it's weird... Since we get Just True as the condition result, shouldn't we get Just 1 ? Why do we have Nothing as a result ? Well, it is because we are not doing things in sequence.

In an imperative language, we are used to see these constructs often:

function doSomethingToFirstElement(array, f) {
  if (array.length > 0) {
    let x = array[0];
    f(x);
  } else {
    console.log("first element does not exist");
  }
}

In this example, the if structure choses between two programs to execute. We don't call them programs but branches or code blocks or even statements, but the important thing here is that they are not executed yet, the if statement choses which branch to execute next. So it will work, because the branch that tried to read the first element of the array will never be executed if the array is empty.

But in Haskell, we work with values, not programs. So in order to call ifThenElseA, we need to have its 3 arguments already computed. If we develop (beta-reduce) the expression ifThenElseA (Just True) Nothing (Just 2), we get this:

case (Just True) of
  Nothing -> Nothing

  --        see, here, the second argument is directy matched, and outputs Nothing
  --        because we bypass everything
  Just p -> case Nothing of
    Nothing -> Nothing
    Just y -> case (Just 2) of
      Nothing -> Nothing

      --        and below here, we have the if then else expression
      --        which will be evaluated only if all arguments are Just
      Just n -> if p then y else n

A solution for the Maybe type

If we want our code to have a similar semantic as the JavaScript code above, we would need a function that develops to this:

case maybeP of
  Nothing -> Nothing
  Just p -> if p then maybeY else maybeN

Here, maybeP, is first evaluated, and we chose which of maybeY or maybeN needs to be evaluated next. You can implement a function ifThenElseFixed that does exactly this, and see for yourself.

-- write this in a module
ifThenElseFixed p y n =
  case p of
    Nothing -> Nothing
    Just p -> if p then y else n

λ> -- and try it in ghci
λ> ifThenElseFixed Nothing (Just 1) (Just 2)
Nothing
λ> ifThenElseFixed (Just False) (Just 1) Nothing
Nothing
λ> ifThenElseFixed (Just True) (Just 1) Nothing
Just 1

It works ! We managed to chose which context to evaluate next, based on a previously evaluated context.

The Monad type class

A Monad is a Functor which allows to chose which context to evaluate next, based on a previously evaluated context. Exactly like what we did with ifThenElseFixed earlier. Let's use this abstraction for more useful things, and understand how it allows that.

The case of evalRPNExpression

Recall evalRPNExpression:

evalRPNExpression :: RPNStack -> RPNExpression -> Result RPNStack
evalRPNExpression s [] = s
evalRPNExpression s (sym:syms) =
  case evalRPNSymbol s sym of
    Left err -> Left err
    Right s -> evalRPNExpression s syms

It has roughly the same form as the ifThenElseFixed function we saw earlier. Not convinced ? Look:

evalRPNExpression :: RPNStack -> RPNExpression -> Result RPNStack
evalRPNExpression s [] = s
evalRPNExpression s (sym:syms) =
  case result of
    Left err -> Left err
    Right s -> go s
  where 
    result :: Result RPNStack
    result = evalRPNSymbol s sym
    go :: RPNStack -> Result RPNStack
    go s = evalRPNExpression s syms

ifThenElseFixed :: Maybe Bool -> Maybe x -> Maybe x -> Maybe x
ifThenElseFixed p y n =
  case result of
    Nothing -> Nothing
    Just p -> go p
  where
    result :: Maybe Bool
    result = p
    go :: Bool -> Maybe x
    go p = if p then y else n

Ok, they work on different context types, one is Result (which is an alias for Either String) and the other is Maybe. But the type pattern is the same if we abstract the Functor:

• They both work on a result value of type f a
• They both apply a function go of type a -> f b
• They both return a value of type f b

For evalRPNExpression we have:

• f = Result
• a = RPNSymbol
• b = RPNStack

For ifThenElseFixed we have:

• f = Maybe
• a = Bool
• b = x

It also works with evalRPN, it can be rewritten in terms of result and go:

evalRPN str = case result of
  Left error -> Left error
  Right exp -> go exp
  where
    result :: Result RPNExpression
    result = readRPNExpression str
    go :: RPNExpression -> Result RPNStack
    go exp = evalRPNExpression [] exp

Monad definition

As always, when we study a type class, we first look at its API:

λ> :i Monad
type Monad :: (* -> *) -> Constraint
class Applicative m => Monad m where
  (>>=) :: m a -> (a -> m b) -> m b
  (>>) :: m a -> m b -> m b
  return :: a -> m a
  {-# MINIMAL (>>=) #-}
        -- Defined in ‘GHC.Base’
instance Monoid a => Monad ((,) a) -- Defined in ‘GHC.Base’
instance (Monoid a, Monoid b) => Monad ((,,) a b)
  -- Defined in ‘GHC.Base’
instance (Monoid a, Monoid b, Monoid c) => Monad ((,,,) a b c)
  -- Defined in ‘GHC.Base’
instance Monad ((->) r) -- Defined in ‘GHC.Base’
instance Monad IO -- Defined in ‘GHC.Base’
instance Monad [] -- Defined in ‘GHC.Base’
instance Monad Maybe -- Defined in ‘GHC.Base’
instance Monad Solo -- Defined in ‘GHC.Base’
instance Monad (Either e) -- Defined in ‘Data.Either’

To be a Monad, you need:

• To be a Applicative (class Applicative m => Monad m where)
• To implement the (>>=) operator ({-# MINIMAL (>>=) #-})

Take a closer look at (>>=):

(>>=) :: Monad m => m a -> (a -> m b) -> m b

Does it ring any bell ? Don't remember the types of result and go in previous code ? Yes, that's it, this is exactly the function we need to combine them. It takes some value of type a wrapped in a Monad m, a function that will work on this value and produce a new wrapped value, and it gives the produced value along with a final context (the wrapping Monad). Try rewriting ifThenElseFixed, evalRPNExpression and evalRPN with (>>=):

ifThenElseFixed p y n = result >>= go
  where
    result = p
    go p = if p then y else n

evalRPNExpression s [] = s
evalRPNExpression s (sym:syms) = result >>= go
  where
    result = evalRPNSymbol s sym
    go s = evalRPNExpression s syms

evalRPN s = result >>= go
  where
    result = readRPNExpression s
    go p = evalRPNExpression [] p

Since the expressions are very simple, we can even get rid of result and go objects and just copy paste their definition:

ifThenElseFixed p y n = p >>= (\p -> if p then y else n)

evalRPNExpression s [] = s
evalRPNExpression s (sym:syms) = evalRPNSymbol s sym >>= (\s -> evalRPNExpression s syms)

-- we can even use partial application to make the expression more elegant
evalRPN s = readRPNExpression s >>= evalRPNExpression []

You may already have used Monads in your life if you worked with the Promise type in JavaScript. The operator (>>=) is exactly the same as the .then() method. Imagine if readRPNExpression and evalRPNExpression were async operations, you may have implemented evalRPN as:

async function evalRPN(s) {
    let expr = await readRPNExpression(s);
    return await evalRPNExpression(expr);
}

This is equivalent to this:

function evalRPN(s) {
    return readRPNExpression(s)
        .then((expr) => evalRPNExpression(expr));
}

Yes, async in JavaScript is a Monad ! It encapsulates the whole "chain together functions to call when the result is ready" in this then() method. The implementation could be very complex, it's not your concern, you just have to use then().

Kleisli arrow

Don't run away ! I swear this title is not that scary ! When we worked on pure functions (a -> b) we had lots of helper functions like foldl, or (.) (composition operator) ...

These functions allow us to express powerful programs by combining smaller functions. But by working with Monads we lost them... Or did we ?.. Hey Vsauce... Of course now our functions look like a -> m b instead of a -> b, so we cannot use normal composition anymore. But could we rebuild a special composition operator that works on functions of the shape a -> m b using (>>=) ? (Don't forget to use holes to help you)

(.)      ::            (b ->   c) -> (a ->   b) -> (a ->   c)
mcompose :: Monad m => (b -> m c) -> (a -> m b) -> (a -> m c)

mcompose :: Monad m => (b -> m c) -> (a -> m b) -> (a -> m c)
mcompose f g = \a -> g a >>= f

We talked before about the arrow type, which is a fancy name for functions. Arrows are simple functions from values of some type to values of some other type. They can be combined together to create more complex functions, we saw their power. And arrows of the shape a -> m b, which we can call "monadic" functions have the same powers as a -> b arrows. They real name is Kleisli arrows, named after the mathematician Heinrich Kleisli who discovered them.

So we saw that composition is still possible using these monadic functions. Let's see what other operations we can still do. Before modifying our functions, we implemented evalRPNExpression with the foldl function. Since monadic functions have (at least) the same powers as normal ones, we can have a monadic version of foldl. It is called foldM, and here is its type, compared to foldl type:

foldl :: (Foldable t)          => (b -> a ->   b) -> b -> t a ->   b
foldM :: (Foldable t, Monad m) => (b -> a -> m b) -> b -> t a -> m b

And it is the perfect function to re-implement readRPNExpression as we did before but within the Result monad. Try to implement it:

-- in developed form
evalRPNExpression stack expr = foldM (\stack symbol -> evalRPNSymbol stack symbol) stack expr

-- using partial application
evalRPNExpression = foldM evalRPNSymbol

As always, after modifying the code, we reload the code and test it:

λ> :r
λ> evalRPN "1 2 + 3 *"
Right [9]
λ> evalRPN "1 2 + *"
Left "Stack underflow at symbol *"

And of course it still works, we just changed the very specific code to generic code. This will come in handy later.

Previous chapter Next chapter