OCaml function to evaluate addition and subtraction

Question

I'm currently trying to write an OCaml function that will evaluate expressions and return a Boolean value. I've tried to do research online, and the closest answer that I could find is this one. However, I'm still having trouble which led me to ask my own question.

Here's the basic code:

type equation =
  | True
  | False
  | Equal of exp * exp
and exp =
  | Val of int
  | Add of exp * exp
  | Sub of exp * exp

let rec eval : equation -> bool
= fun f ->
  match f with
  | True -> true
  | False -> false
  | Equal (x, y) -> match (x, y) with
                    | (Val a, Val b) -> if (x = y) then true else false
                    | ((Add (Val a, Val b), c) -> eval (Equal (Val (a + b), c))

The program is incomplete, and the recursive call to eval in the last line is where I got stuck. A specific input example that I've thought of is:

eval (Equal (Add (Add (Val 1, Val 2), Val 3), Val 6))

This should evaluate to true, since the two Add's add up to 6, and Equal compares Val 6 with Val 6. The trouble that I'm experiencing is how to recursively call the function to evaluate the second Add inside the expression, so that Add (Val 2, Val 2) first evaluates to Val 3, then the first Add adds Val 3 with Val 3. The program that I've written right now only evaluates one of the two Add's.

Is there anything that I should be thinking of or keeping in mind? Any feedback is welcome. Thank you.

Why not Equal (x, y) -> eval_exp(x) == eval_exp(y)? Doing both in one is uncomfortable, as you're finding... — Amadan
Hey @Amadan thanks for the feedback. I've tried that as well, but unfortunately I get a type error that says "this has type exp but type equation was expected." — Sean
You have two types; so two evaluating functions would be needed. Note that I didn't use eval. — Amadan
Ah, you're right. Thanks for clarifying. I'll give it a try. — Sean

Ulugbek Abdullaev Ulugbek Abdullaev · Accepted Answer · 2018-09-25T07:02:22

As @Amadan mentioned, it's easier to define a function that would first evaluate expression to an int eval_exp: exp -> int. Then you can just evaluate both expressions in the tuple Equal(e1, e2) and compare them (eval: equation -> bool).

You also do not need values True and False in type equation, because you can just return bool from function without pattern-matching. Note that you could need True and False if you passed those, for some reason, again to eval function.

type equation =
  Equal of exp * exp
and exp =
  | Val of int
  | Add of exp * exp
  | Sub of exp * exp

let rec eval (e: equation) : bool =
  let rec eval_exp e =
    match e with
    | Val i -> i
    | Add (e1, e2) -> (eval_exp e1) + (eval_exp e2)
    | Sub (e1, e2) -> (eval_exp e1) - (eval_exp e2)
  in
  match e with
  | Equal (e1, e2) ->
      if (eval_exp e1) = (eval_exp e2)
      then true
      else false

OCaml function to evaluate addition and subtraction

1 Answers