Maybe monad construction

Question

I'm currently struggling with a new element of Haskell: Monads. Therefore I was introduced to this by an example of creating a (>>=) operator that executes a function on a Maybe type (taking its actual integer value as argument to it) only if it's not equal to Nothing, and otherwise return Nothing:

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

However, I'm not quite sure how this works with the following usage of it:

eval (Val n) = Just n
eval (Div x y) = eval x >>= (\n ->
    eval y >>= (\m ->
        safediv n m))

It seems to me that the (>>=) operator simply takes one Maybe value and a function that returns one, however in this example usage code it seems like it's taking 2 times a Maybe value and once a function. I was told however that it evaluates x, puts the result in n, then evaluates y, puts the result in y, and then executes the safediv function on both. Although I don't see how the (>>=) operator plays its role here; How does this work?

Answer 1

You can read it like this:

eval (Div x y) = eval x >>= (\n ->
    eval y >>= (\m ->
        safediv n m))

when you want do eval (Div x y)then

• first eval x:
• • if was Just n (using the first >>=)
• • then take the n and have a look at eval y (using the first >>=)
• • • if the last is Just m (second >>=)
• • • then take the m and do a (second >>=)
• • • savediv n m to return it's result - you still have the n from your closure!.

in ever other caes return Nothing

So here the (>>=) just helps you to deconstruct.

Maybe it's easier to read and understand in the do form:

eval (Val n) = Just n
eval (Div x y) = do
    n <- eval x
    m <- eval y
    safediv n m

which is just syntactic sugar around (>>=)

let's chase the cases:

1. eval x = Nothing and eval y = Nothing:

eval x >>= (...) = Nothing >>= (...) = Nothing

2. eval x = Nothing and eval y = Just n:

which is just the same:

eval x >>= (...) = Nothing >>= (...) = Nothing

3. eval x = Just n and eval y = Nothing:

eval x >>= (\n -> eval y >>= (...))
= Just n >>= (\n -> eval y >>= (...)) 
= Just n >>= (\n -> Nothing)
= Nothing

4. eval x = Just n and eval y = Just m:

eval x >>= (\n -> Just m >>= (...))
= Just n >>= (\n -> Just m >>= (...)) 
= Just n >>= (\n -> Just m >>= (\m -> safediv n m))
= (first >>= for Just) = Just m >>= (\n -> safediv n m)
= (second >>= for Just) = safediv n m

Answer 2

you have

eval (Val n) = Just n

from this we conclude that eval produces a Maybe value. The second equation, let's rewrite it as

eval (Div x y) = 
  eval x >>= (\n ->
                    eval y >>= (\m ->
                                      safediv n m ) )

i.e.

eval (Div x y) = 
  eval x >>= g 
             where
             g n =  eval y >>= h 
                               where
                               h m =  safediv n m

See? There is only one function involved in each >>= application. At the top, it's g. But g defines – and uses – h, so h's body has access both to its argument m and the g's argument, n.

If eval x produced Nothing, then eval x >>= g is just Nothing, immediately, according to the >>= definition for the Maybe types (Nothing >>= _ = Nothing), and no eval y will be attempted.

But if it was (Just ...) then its value is just fed to the bound function (Just x >>= f = f x).

So if both evals produce Just ... values, safediv n m is called inside the scope where both arguments n and m are accessible. It's probably defined as

safediv :: Num a => a -> a -> Maybe a
safediv n m | m == 0    =  Nothing
            | otherwise =  Just (div n m)    -- or something

and so h :: m -> Maybe m and g :: n -> Maybe n and the types fit,

-- assuming a missing type of "expressions", `Exp a`,
eval :: Num a => Exp a ->                                       Maybe a    
  -- Num a is assumed throughout, below
  eval (Div x y) =                                           -- Maybe a
  -- Maybe a >>= a ->                                           Maybe a
      eval x >>= g 
                 where
  --               a ->                                         Maybe a
  --                   Maybe a >>= a ->                         Maybe a 
                 g n =  eval y >>= h
                                   where
  --                                 a ->                       Maybe a
                                   h m =  safediv    n    m  -- Maybe a
  --                                      safediv :: a -> a ->  Maybe a

as per the type of bind for the Maybe monad,

(>>=) :: Maybe a -> 
              (a -> Maybe b) -> 
         Maybe            b

Answer 3

Let's do element chasing to illustrate how it works. If we have

eval (Div (Val 5) (Div (Val 0) (Val 1)))

Then we can break this down into

eval (Div (Val 5) (Div (Val 0) (Val 1)))
    = eval (Val 5) >>=
        (\n ->
            eval (Div (Val 0) (Val 1)) >>=
                (\m ->
                    safediv n m
                )
        )

-- eval (Val 5) = Just 5

    = Just 5 >>=
        (\n ->
            eval (Div (Val 0) (Val 1)) >>=
                (\m ->
                    safediv n m
                )
        )

-- Just x >>= f = f x

    = (\n ->
        eval (Div (Val 0) (Val 1)) >>=
            (\m ->
                safediv n m
            )
      ) 5

-- Substitute n = 5, since the 5 is the argument to the `\n ->` lamba

    = eval (Div (Val 0) (Val 1)) >>=
        (\m ->
            safediv 5 m
        )

Now we need to take a detour to compute eval (Div (Val 0) (Val 1))...

eval (Div (Val 0) (Val 1))
    = eval (Val 0) >>=
        (\n ->
            eval (Val 1) >>=
                (\m ->
                    safediv n m
                )
        )

-- eval (Val 0) = Just 0
-- eval (Val 1) = Just 1

eval (Div (Val 0) (Val 1))
    = Just 0 >>=
        (\n ->
            Just 1 >>=
                (\m ->
                    safediv n m
                )
        )

-- Just x >>= f = f x

eval (Div (Val 0) (Val 1))
    = (\n ->
        (\m ->
            safediv n m
        ) 1
      ) 0

    = (\n -> safediv n 1) 0
    = safediv 0 1
    = Just 0

And now back to our original call to eval, substituting Just 0 in:

eval (Div (Val 5) (Div (Val 0) (Val 1)))
    = Just 0 >>= (\m -> safediv 5 m)

-- Just x >>= f = f x

eval (Div (Val 5) (Div (Val 0) (Val 1)))
    = safediv 5 0

-- safediv x 0 = Nothing

eval (Div (Val 5) (Div (Val 0) (Val 1)))
    = Nothing