Haskell Monad task

user_14033726 0
Viewed 139

So we have following Data Types:

data Expr = Num Double | Add Expr Expr | Var Char deriving Show

and

type Env = [(Char, Double)]

Further More we have these two functions:

evalDo :: Env -> Expr -> Maybe Double
evalDo _ (Num a) = return a
evalDo e (Var c) = getvar e c
evalDo e (Add a b) = do
    a' <- evalDo e a
    b' <- evalDo e b
    Just (a'+b')

and

getvar :: Env -> Char -> Maybe Double
getvar [] c = Nothing
getvar ((x,y):es) c 
    | c == x = Just y
    |otherwise = getvar es c

So if we would run the following Code: evalDo [('x', 2)] (Add (Num 5) (Var 'x')), we would receive:Just 7.0. Whereas evalDo [('x', 2)] (Add (Num 5) (Var 'y')) evaluates to Nothing.

From what I understand when running the former code, our function matches the evalDo e (Var c) = getvar e c line. From there it calls getvar e c which results in Just 2. Then we go back to our original second call, which is (Add (Num 5) (Var 'x'))

. Now the Var 'x' is resolved into Just 2. So finally the evalDo e (Add a b) = do... function-line matches and we get Just7.0.

Obviously there is a huge major flaw to my explanation, since we try to "Add" Num 5 and Just 2 and by our definition its not possible. Yet the function seems to work flawelessly somehow but I just can't figure it out.

monads haskell
2 Answers

Let's break this down into steps. First, do notation isn't magic in Haskell. It desugars to ordinary operators. So let's look at your last case in evalDo.

evalDo e (Add a b) = do
    a' <- evalDo e a
    b' <- evalDo e b
    Just (a'+b')

By the destructuring rules, this is equivalent to

evalDo e (Add a b) =
    evalDo e a >>= \a' ->
    evalDo e b >>= \b' ->
    Just (a' + b')

So, when we call evalDo [('x', 2)] (Add (Num 5) (Var 'x')), we first match the Add a b line. We'll do that case with a = Num 5 and b = Var 'x'. Inside of that branch, we evalDo both a and b.

But we do not assign the results to variables. If we had used let, then a' would be equal to Just 5 and b' to Just 2. But that's not what happens. We used <-, which desugars to a monadic bind. Let's take the first evalDo. It looks like this.

evalDo e a >>= \a' -> ...

The evalDo part returns Just 5. The >>= operator (usually pronounced "bind") on Maybe is defined as

(Just x) >>= k      = k x
Nothing  >>= _      = Nothing

If the left-hand evaluates to a Just, then the right-hand (which is a function) is called with the inside of that Just as an argument. If the left-hand evaluates to Nothing, then the right-hand (which is, again, a function) is never called.

In our case, evalDo e a evaluated to Just 5, so we call the lambda function with argument 5. The lambda calls its argument a', so we have a' equal to 5, the inside of the Just.

The same thing happens in the second case, with Just 2 instead of Just 5. If we had given it a variable name that didn't exist, then we would get a Nothing, the lambda would never be called, and the entire function would return Nothing. The do notation just makes all of this higher-order function nonsense transparent, so we don't have to think about it as much.

evalDo e (Add a b) = do
    a' <- evalDo e a
    b' <- evalDo e b
    Just (a'+b')

Going back to this, the way you should read this normally is "evaluate a, evaluate b, and return a' + b'". The <- bindings carry some context with them. In your case, that context is failure via Maybe, but in principle it could be a local variable, nondeterminism, or even a continuation. The way this is implemented is via lambdas, but in the usual course of programming in Haskell and writing do notation, you don't think about it as such.

user_22886590

I think the part you are missing is that <- is not simply an assignment operator; it "opens" the Just value and binds what it finds to a' and b'. Desugaring the do block gives

evalDo e (Add a b) = 
    evalDo e a >>= \a' -> 
    evalDo e b >>= \b' -> 
    Just (a' + b')

Let's look at >>= for Maybe types.

Nothing >>= _ = Nothing
Just x >>= f = f x -- Call f on x, not on Just x

If evalDo e a produces Nothing, we can ignore the rest of the do block and evaluate directly to Nothing. But if it's a Just 5, we bind 5 (not Just 5) to a' and continue. The same thing happens with evalDo e b: either we get Just 2, bind 2 to b', and continue, or immediately return Nothing.

Only if both recursive calls produce Just values do we reach the final line where we can now add 5 + 2 and wrap the result in Just.

user_11268410
Related