functional-programmingsmlsmlnjml

How can I write a function to evaluate custom datatype


datatype mixed_expression =
   ME_NUM of int
 | ME_PLUS of mixed_expression * mixed_expression
 | ME_TIMES of mixed_expression * mixed_expression
 | ME_LESSTHAN of mixed_expression * mixed_expression;

datatype value =
   INT_VAL of int
 | BOOL_VAL of bool
 | ERROR_VAL;

I am given these data types and this is my approach

fun eval e = 
  case e of 
    ME_NUM x       => INT_VAL x 
  | ME_PLUS (l, r) => eval l + eval r

I got the following error message.

**Error: overloaded variable not defined at type
  symbol: +
  type: value**

I have no clues on how to solve these issues since I am not allowed to use mutation.


Solution

  • The error message tells you what you need to know. When you write:

    eval l + eval r
    

    The expressions eval l and eval r yield type value. There is no + operator for this type.

    As a style note, your case is extraneous in this situation.

    fun eval(ME_NUM x)       = INT_VAL x
      | eval(ME_PLUS (l, r)) = eval l + eval r
    

    You should also get a warning about pattern-matching being non-exhaustive as you haven't handled ME_TIMES or ME_LESSTHAN.

    Really, what you need to do is define a function which can add two value values.

    fun me_add(INT_VAL a, INT_VAL b)  = INT_VAL (a + b)
      | me_add(INT_VAL a, BOOL_VAL b) = (* ... *)
    

    There are lots of combinations you'll need to pattern-match on. You may want to just define a function that coerces a value into an int.

    fun toInt(INT_VAL a)      = a
      | toInt(BOOL_VAL True)  = 1
      | toInt(BOOL_VAL False) = 0
      | (* and so on... *)
    

    Then you could write something like:

    fun me_add(a, b) = INT_VAL(toInt a + toInt b)