How do you define the monad instance for the following data types?

Question

Here's the code I have to work with:

infixl 9 :@: -- This is newly defined symbol used in the application of expressions

data Expr
  =  Lit Integer      -- a literal
  |  Var String       -- a variable
  |  Bin Expr Op Expr -- binary operator
  |  Abs String Expr  -- a lambda expression
  |  Expr :@: Expr    -- an application
  deriving Show

data Op = Plus | Mult
  deriving Show

data Value = IntVal Integer | FunVal Env String Expr
  deriving Show

type Env = [(String,Value)]

applyIntOp :: Op -> Value -> Value -> Value
applyIntOp op (IntVal v1) (IntVal v2) = 
   case op of 
      Plus -> IntVal (v1 + v2)
      Mult -> IntVal (v1 * v2)

eval :: Expr -> Env -> Value
eval (Lit i)        env = IntVal i
eval (Var v)        env = fromJust (lookup v env)
eval (Bin e1 op e2) env = applyIntOp op (eval e1 env) (eval e2 env)
eval (Abs v b)      env = FunVal env v b
eval (ef :@: ea)    env = let FunVal env var body = eval ef env
                              arg                 = eval ea env
                           in eval body ((var,arg):env) 

The goal is to make an evaluation function such that it can use variables (Var String), of which the variables are taken from the environment (Env). However when I try to define a monad with any of these types, I can't because they don't have the correct kind (* instead of * -> *).

So, how would I go about defining this Monad such that I can use it to evaluate any expressions correctly.

instance Monad ? where
  return = ..
  >>=    = .. 

As an example (3 + (x * 4)(apply)(x=1+2)):

eval (Bin (Lit 3) Plus ((Abs "x" (Bin (Var "x") Mult (Lit 4))) :@: Bin (Lit 1) Plus (Lit 2))) []

This returns 15

Answer 1

As a side note, your eval (ef :@: ae) case is wrong, since you're using the wrong copy of env in evaluating ef and ea. You want this instead:

eval (ef :@: ea)    env = let FunVal env' var body = eval ef env
                              arg                  = eval ea env
                           in eval body ((var,arg):env')

Anyway, let's start by discussing the usual way of "using a monad" for an evaluation function like eval.

Your eval function has signature:

eval :: Expr -> Env -> Value

Even though it's primary purpose is to take an Expr and determine its Value (i.e., it's basically a function Expr -> Value), you have some extra information you need to carry around, namely this Env that describes variable bindings. Even though you only access these bindings when processing Var and Sub constructors and only modify these bindings when processing :@: constructors, you still need to pass Env around for all the cases that don't care about it, especially cases like:

eval (Bin e1 op e2) env = applyIntOp op (eval e1 env) (eval e2 env)

which don't even touch env, but need to pass it along to every recursive eval call.

To avoid this, what folks usually do is introduce a monadic context for their evaluation. This does not involve writing a monad instance for Expr or Env or Value. Rather, it involves changing the signature of eval to take an Expr and return a Value, but in a "monadic context" that can make Env available for inspection and modification:

evalM :: Expr -> MyMonad Value

There's a actually a ready-made monad for this, so you don't have to write your own:

import Control.Monad.Reader
type MyMonad = Reader Env

After this, it's somewhat easier to write the cases that don't care about Env:

evalM (Lit i) = pure $ IntVal i
evalM (Bin e1 op e2) = applyIntOp op <*> eval e1 <*> eval e2

and the cases that do care about Env don't look too bad either:

evalM (Var v) = asks (fromJust . lookup v)
evalM (Abs v b) = FunVal <$> ask <*> pure v <*> pure b
evalM (ef :@: ea) = join $ apply <$> evalM ef <*> evalM ea
  where apply (FunVal env var body) va =
          local (const ((var,va):env)) $ evalM body

Admittedly, introducing MyMonad doesn't help very much in this example, but if you decided to extend your language to support mutable values, error handling, and IO side effects, you'd start to see more advantages to this approach.

Again, this is the usual way of using a monad for evaluation, but I'm not sure if this is what you were asking about or not.

An unusual way of using a monad for evaluation would be to write a monad instance for an Expr type where the monadic action is some kind of "substitution". It's really hard to imagine how this would work. The most obvious starting point would be to consider the way a monad is often used to recursively replace elements of a structure without changing the overall structure. For example, the list monad can be viewed as replacing each element of a list with a new list, but instead of returning a list of lists, it concatenated it all together to give it the same type as the origin. For trees with values at the leaves, there's a usual monad that replaces each leaf with an associated tree, but instead of giving a tree of trees, the structure is flattened out so it's just a tree of the same type as the original.

From this starting point, it's easy to imagine a substitution monad for expressions where the leaves are the variable references:

data ExprM a
  =  LitM Integer
  |  VarM a
  |  BinM (ExprM a) Op (ExprM a)
  deriving (Show, Functor)

The monadic action can be to substitute each VarM a (leaf) with an ExprM a (tree):

instance Applicative ExprM where
  pure = VarM
  (<*>) = ap
instance Monad ExprM where
  VarM x >>= f = f x
  LitM n >>= f = LitM n
  BinM e1 op e2 >>= f = BinM (e1 >>= f) op (e2 >>= f)

Note that there is no AppM constructor because it's been replaced by the monadic bind. If you want to substitute LitM 1 for the value of VarM "x" in the expression BinM (VarM "x") Plus (VarM "x"), you do it like so:

body1 = BinM (VarM "x") Plus (VarM "x")

context1 "x" = LitM 1
context1 _ = error "variable not found"

example1 = body1 >>= context1

which gives:

> example1
BinM (LitM 1) Plus (LitM 1)

The problem is that it's not at all clear how to add the Abs constructor back in. It can't really have form:

... | Abs a (ExprM a) | ...

because the only sensible monad instance would have to perform substitution on the argument name, which doesn't make any sense. It would also be susceptible to variable capture.

If there's some clever representation for Abs that lets you stick with a monadic substitution scheme, I'm not seeing it.