Home > Software design >  Understanding Haskell laziness in case of "if then else"
Understanding Haskell laziness in case of "if then else"

Time:09-04

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 ||.

  • Related