Haskell Monad task

Question

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.

Not an answer to your question, really, but you might be interested to try puzzling through the equivalent applicative-style implementation too: evalDo e (Add a b) = liftA2 (+) (evalDo e a) (evalDo e b). Or the alternative with punctuation instead of parens: evalDo e (Add a b) = (+) <$> evalDo e a <*> evalDo e b. — amalloy
– amalloy, Commented Jul 26, 2022 at 20:18

Silvio Mayolo · Accepted Answer · 2022-07-26 20:11:40Z

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.

chepner · Accepted Answer · 2022-07-26 20:21:00Z

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.

Collectives™ on Stack Overflow

Haskell Monad task

2 Answers 2

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Related