avoid explicit passing of lookup table

Question

In my very simple boolean expression toy program, I have the following evaluation function:

eval' :: Expr -> M.Map Char Bool -> Bool

eval' (Const c) values = c

eval' (Var v)   values = M.findWithDefault False v values

eval' (Not x)   values = not (eval' x values)

eval' (And a b) values = eval' a values && eval' b values

eval' (Or  a b) values = eval' a values || eval' b values

eval' (Xor a b) values = eval' a values /= eval' b values

I was wondering if there was a way to pass the values table implicitly? Maybe with the help of Monads?

Answer 1

Monads would work, but in my opinion using Applicative is cleaner here:

eval' :: Expr -> M.Map Char Bool -> Bool
eval' (Const c) = pure c
eval' (Var v)   = M.findWithDefault False v
eval' (Not x)   = not <$> eval' x
eval' (And a b) = (&&) <$> eval' a <*> eval' b 
eval' (Or  a b) = (||) <$> eval' a <*> eval' b
eval' (Xor a b) = (/=) <$> eval' a <*> eval' b

This is using the ((->) r) instance, like the Reader monad/applicative, but without the newtype wrapper.

Answer 2

This is exactly what the Reader monad is for:

The Reader monad (also called the Environment monad). Represents a computation, which can read values from a shared environment, pass values from function to function, and execute sub-computations in a modified environment.

As Sjoerd notes, the monad gives more power here than you need, but you can still use the Reader monad for this problem without so much as typing do:

import qualified Data.Map as M

import Control.Applicative ( (<$>), (<*>) )
import Control.Monad.Reader

data Expr = Const Bool
          | Var Char
          | Not Expr
          | And Expr Expr
          | Or Expr Expr
          | Xor Expr Expr

Just put your environment type as the first argument to the Reader type constructor, and your original result type as the second.

eval' :: Expr -> Reader (M.Map Char Bool) Bool

Instead of just c as the value of the Const case, use return to lift it into the monad:

eval' (Const c) = return c

When you need the environment for looking up the value of a variable, use ask. Using do notation, you can write the Var case like this:

eval' (Var v)   = do values <- ask
                     return (M.findWithDefault False v values)

I think it's nicer, though, to use fmap a.k.a. <$>:

eval' (Var v)   = M.findWithDefault False v <$> ask

Similarly, the unary not can be fmapped over the result of the recursion:

eval' (Not x)   = not <$> eval' x

Finally, the Applicative instance of Reader makes the binary cases pleasant:

eval' (And a b) = (&&) <$> eval' a <*> eval' b

eval' (Or  a b) = (||) <$> eval' a <*> eval' b

eval' (Xor a b) = (/=) <$> eval' a <*> eval' b

Then, to get it all started, here's a helper to create the initial environment and run the computation:

eval :: Expr -> [(Char,Bool)] -> Bool
eval exp env = runReader (eval' exp) (M.fromList env)

Answer 3

In this case, do not pass values at all:

eval' :: Expr -> M.Map Char Bool -> Bool
eval' e values = eval'' e

    where
    eval'' (Const c) = c
    eval'' (Var v) = M.findWithDefault False v values
    eval'' (Not x) = not (eval'' x)
    ...

Answer 4

Do you know the extension implicit parameters? It could be quite helpful.