'Unpacking' the data in an SML DataType without a case statement

Question

I have an SML program which represents a language with Expressions that are comprised of Values:

datatype Value = IntVal of int
               | ListVal of Value list

datatype Exp = Const of Value
             | Plus of Exp * Exp
             | Minus of Exp * Exp
             | Times of Exp * Exp

I'm also writing an eval function that converts an expression into a value. If the expression is a Plus expression (e.g. Plus (Const (IntVal 1), Const (IntVal 1)) which represents 1+1), I just want to take out the integer stored in the IntVal and just add them together and return that.

But as far as I can tell, I have to have a seemingly redundant case statement with only one case just to get at the integer inside the IntVal data type:

(*Evaluates an Exp and returns a Value*)
fun eval e =
  (*Evaluate different types of Exp*)
  case e of
      (*If it's a constant, then just return the Value*)
      Const v => v
      (*If it's a Plus, we want to add together the two Values*)
    | Plus (x,y) =>
         (*Case statement with only one case that seems redundant*)
         case (eval x, eval y) of
            (IntVal xVal, IntVal yVal) => IntVal (xVal + yVal)

Is there no easy way to do simplify this? I'd like to do something like this, which of course isn't valid SML:

fun eval e =
  case e of
      Const v => v
    | Plus (x,y) => IntVal (eval x + eval x)

Answer 1

If you want your eval function to return an int and you haven't figured out how to get an int from a Value which uses the ListVal constructor -- it is enough to just supply patterns which correspond to the cases that your intended definition covers.

fun eval (Const (IntVal v)) = v
|   eval (Plus (e1,e2)) = eval(e1) + eval(e2)
|   eval (Minus (e1,e2)) = eval(e1) - eval(e2)
|   eval (Times (e1,e2)) = eval(e1) * eval(e2);

SML/NJ gives Warning: match nonexhaustive - but if it matches your intention then you can ignore the warning.

The above code returns an int. If you want to return values which look like e.g. IntVal 3 then you could define 3 functions which take pairs of IntVals and return IntVals corresponding to their sums, differences, and products and use these functions on the right hand sides of the above definition.

Answer 2

Yes, there are at least two ways to simplify this: Exceptions, or monads.

The problem you have is that eval (Const (ListVal [...])) does not have a meaningful integer value. To ensure that this remains a total function (one for which all input values result in an output value, as opposed to a partial function), its type could instead be expressed as:

val eval : Exp -> int option

You could implement this most easily by using exceptions:

local
  fun eval' (Const (IntVal v)) = v
    | eval' (Const (ListVal _)) = raise Domain
    | eval' (Plus (e1, e2)) = eval' e1 + eval' e2
    | eval' (Minus (e1, e2)) = eval' e1 - eval' e2
    | eval' (Times (e1, e2)) = eval' e1 * eval' e2
in
  fun eval e = SOME (eval' e) handle Domain => NONE
end

Or you could implement this by complicating your recursive function:

fun eval (Const (IntVal v)) = SOME v
  | eval (Const (ListVal _)) = NONE
  | eval (Plus (e1, e2)) =
    (case (eval e1, eval e2) of
          (SOME v1, SOME v2) => SOME (v1+v2)
        | _ => NONE)
  | eval (Minus (e1, e2)) =
    (case (eval e1, eval e2) of
          (SOME v1, SOME v2) => SOME (v1-v2)
       |  _ => NONE)
  | eval (Times (e1, e2)) =
    (case (eval e1, eval e2) of
          (SOME v1, SOME v2) => SOME (v1*v2)
        | _ => NONE)

Clearly that is not easy or pretty.

One way to improve this code is to abstract a common, repetitive pattern into a function:

fun evalBinop (f, e1, e2) =
    case (eval e1, eval e2) of
         (SOME v1, SOME v2) => SOME (f (v1, v2))
       | _ => NONE
and eval (Const (IntVal v)) = SOME v
  | eval (Const (ListVal _)) = NONE
  | eval (Plus (e1, e2)) = evalBinop (op+, e1, e2)
  | eval (Minus (e1, e2)) = evalBinop (op-, e1, e2)
  | eval (Times (e1, e2)) = evalBinop (op*, e1, e2)

Here evalBinop depends on calling back on eval, so I made them mutually recursive. I also rely on interpreting binary operators as functions that take tuples as arguments.

An improvement comes in making more generic helper functions that handles the 'a option type:

infix 3 >>=
fun NONE >>= _ = NONE
  | (SOME a) >>= f = f a

fun liftM2 f (opt1, opt2) =
    opt1 >>= (fn x1 => opt2 >>= (fn x2 => SOME (f (x1, x2))))

fun eval (Const (IntVal v)) = SOME v
  | eval (Const (ListVal _)) = NONE
  | eval (Plus (e1, e2)) = liftM2 (op+) (eval e1, eval e2)
  | eval (Minus (e1, e2)) = liftM2 (op-) (eval e1, eval e2)
  | eval (Times (e1, e2)) = liftM2 (op* ) (eval e1, eval e2)

At this point, >>= and liftM2 are useful functions that don't depend on the notion of evaluating an expression or applying integer operators. They're not present in Standard ML's library, but they should be. At this point I incidentally re-invented monads.

A last improvement comes by adding a little syntax sugar, which is most likely overkill:

infix 7 **
infix 6 ++
infix 6 --
val op** = liftM2 op*
val op++ = liftM2 op+
val op-- = liftM2 op-

fun eval (Const (IntVal v)) = SOME v
  | eval (Const (ListVal _)) = NONE
  | eval (Plus (e1, e2)) = eval e1 ++ eval e2
  | eval (Minus (e1, e2)) = eval e1 -- eval e2
  | eval (Times (e1, e2)) = eval e1 ** eval e2

(A few examples demonstrating exactly what it is >>= and liftM2 do...)

(* 'x >>= f' means:
 *     if x is 'NONE', just return NONE
 *     if x is 'SOME a', apply f to a, and expect f to return either 'SOME b' or 'NONE' *)
(* For example, this should give 'SOME 4': *)
val example_1 = SOME 3 >>= (fn x => SOME (x+1))

(* And these should both give 'NONE': *)
val example_2 = NONE >>= (fn x => SOME (x+1))
val example_3 = SOME 3 >>= (fn x => NONE)

(* If 'f : t1 * t2 -> t3', then 'liftM2 f : t1 option * t2 option -> t3 option' *)
val _ = op+ : int * int -> int
val _ = liftM2 op+ : int option * int option -> int option

(* For example *)
val example_4 = liftM2 op+ (SOME 3, SOME 4)  (* gives SOME 7 *)
val example_5 = liftM2 op- (SOME 10, NONE)   (* gives NONE *)
val example_6 = liftM2 op* (NONE, SOME 5)    (* gives NONE *)