back - up - next

Algebraic Datatypes

1. Grammar as Datatypes
   The "information" contained in the expression "e=1+(2*3)" can be formalized by the following type definition:

type Exp = Val of int | Plus of Exp*Exp | Mult of Exp*Exp;;  

let e = Plus (Val 1,Mult (Val 2, Val 3));;

2. "Interpretation" is then a particular function:

let rec interp e = 
  match e with
  | Val v        -> v
  | Plus (e1,e2) -> (interp e1)+(interp e2)
  | Mult (e1,e2) -> (interp e1)*(interp e2);;

interp e;;

10