(* an example of some expression optimization in OCaml; see alg.py for
   original context *)

type num = Int of int | Float of float
type expr = Sum of expr * expr | Product of expr * expr | Const of num

let rec multiply x y = Product (x, y)
and add x y = match (x, y) with
  | (a, Sum(Product(Const k, a'), c)) when a == a' ->
      add (multiply (add (Const (Int 1)) (Const k)) a) c 
  | (Product(Const k, y'), _) when y == y' ->
    multiply (add (Const k) (Const (Int 1))) y 
  | (_, Product(Const k, x')) when x == x' ->
    multiply (add (Const k) (Const (Int 1))) x 
  | (Product (Const k, a), Product (Const k', b)) when a == b ->
    multiply (add (Const k) (Const k')) a 
  | _ -> Sum(x, y)