Currently I'm trying to learn Haskell by following a FP in Haskell course from University of Pennsylvania. In one of the assignments, I had to define the following type classes to implement expression evaluating calculator :
class Expr a where
mul :: a -> a -> a
add :: a -> a -> a
lit :: Integer -> a
class HasVars a where
var :: String -> a
And a data type which mimics a math expression which can contain, addition, multiplication of integers and also can hold a variable in the expression.
data VarExprT = VarLit Integer
| VarAdd VarExprT VarExprT
| VarMul VarExprT VarExprT
| Var String
deriving (Show, Eq)
instance HasVars VarExprT where
var = Var
instance Expr VarExprT where
lit = VarLit
add = VarAdd
mul = VarMul
Now to simulate the operations of adding, multiplying in an expression with variables, I had to create instances of above typeclasses as below :
instance HasVars (M.Map String Integer -> Maybe Integer) where
var str = \mMap -> M.lookup str mMap
instance Expr (M.Map String Integer -> Maybe Integer) where
lit x = \mMap -> Just x
add f1 f2 = \mMap -> if isNothing (f1 mMap) || isNothing (f2 mMap)
then
Nothing
else
Just (fromJust (f1 mMap) fromJust (f2 mMap))
mul f1 f2 = \mMap -> if isNothing (f1 mMap) || isNothing (f2 mMap)
then
Nothing
else
Just (fromJust (f1 mMap) * fromJust (f2 mMap))
And to actually evaluate expressions the below function was provided :
withVars :: [(String, Integer)] -> (M.Map String Integer -> Maybe Integer)-> Maybe Integer
withVars vs exp = exp $ M.fromList vs
So using above function in ghci looks like below :
*Calc> withVars [("x", 6)] $ add (lit 3) (mul (lit 6) (var "x"))
Just 39
*Calc> withVars [("x", 6)] $ add (lit 3) (var "y")
Nothing
So my query is the following :
In a normal expression in Haskell, expressions are evaluated only when they are needed which is still not very intuitive to me, but I sort of get it. But in first expression above, how will it the internal evaluation work for the expression in the condition ?
Because as I understand, first add
is taking place so the if
condition will be checked.
And the condition will have to get evaluated to a point where it comes to True
or evaluate fully to False
. But in the second expression of the ||
it is going to try to evaluate the mul
expression (mul (lit 6) (var "x")) mMap
corresponding to f2 mMap
.
And now again there is an if
condition in mul
. So I'm confused as to how exactly will the evaluations play out because of the recurring if
conditions coming in the middle of expression evaluations.
PS : The M.Map and so on is because of import qualified Data.Map as M
CodePudding user response:
The definition of ||
is lazy, and will evaluate the second argument only when needed, i.e. when the first argument is false.
You can test it in GHCi, observing that the following does not trigger the error.
> True || error "ouch!"
True
In your case, isNothing (f1 mMap) || isNothing (f2 mMap)
will first evaluate isNothing (f1 mMap)
and if that is true it will skip the evaluation of isNothing (f2 mMap)
.
Note that this is essentially the same "short-circuiting" semantics of the boolean operator ||
which is commonly found in C, C , Java, and many other languages. There, evaluating f() || g()
won't call g
unless f()
evaluates to false.
Minor digression on the style
You shouldn't use fromJust
-- that's a partial function that can crash the program if you forget to check for Nothing
. In your code you do check against that, but that's not the recommended style.
You code suffers from "boolean blindness": you have two Maybe Integer
values, and instead of testing them directly, you first transform them into boolean, losing precious information (the integer inside). Since you lost that information in the test, you then need to resort to dangerous tools like fromJust
to recover the information you lost in the test.
The common practice here is to avoid booleans, avoid if
, and use pattern matching to test the Maybe Integer
values directly.
add f1 f2 = \mMap -> case (f1 mMap, f2 mMap) of
(Nothing, _ ) -> Nothing
(_ , Nothing) -> Nothing
(Just i1, Just i2) -> Just (i1 i2)
(There are library functions to shorten that, but it's irrelevant).
The code above uses no booleans at all. It also will evaluate f2 mMap
only when needed, i.e. only if the (_ , Nothing) -> Nothing
line is reached, i.e. only when f1 mMap
was not a Nothing
. This provides the same lazy semantics as the previous code using booleans and ||
.