maths.ml

type exp =
  | EInt of int
  | EAdd of exp * exp
  | EMul of exp * exp;;

let example =
    EAdd (EInt 1, EMul (EInt 2, EInt 3));;


(*
Write the expression 2 * 2 + 3 * 3 in a variable my_example.
*)

let my_example = EAdd (
    EMul (EInt 2, EInt 2),
    EMul (EInt 3, EInt 3)
    )
;;

(*
Write a function eval : exp -> int that computes the value of an arithmetic expression. The evaluation rules are:
    - If the expression is an integer x, the evaluation is x.
    - If the expression is lhs + rhs and lhs evaluates to x and rhs evaluates to
    y, then the evaluation is x + y.
    - If the expression is lhs * rhs and lhs evaluates to x and rhs evaluates
    to y, then the evaluation is x * y.
*)

let rec eval expression = match expression with
EInt x -> x |
EAdd (x, y) -> (eval x) + (eval y) |
EMul (x, y) -> (eval x) * (eval y);;



(*
If an expression is of the form a * b + a * c then a * (b + c) is a
factorized equivalent expression. 

Write a function factorize : exp -> exp that implements this transformation on
its input exp if it has the shape a * b + a * c or does nothing otherwise.
*)

let factorize (expression : exp) : exp = match expression with
EAdd (EMul (a1, a2), EMul (b1, b2)) when a1 = b1 ->
    EMul (a1, (EAdd (a2, b2))) |
EAdd (EMul (a1, a2), EMul (b1, b2)) when a1 = b2 ->
    EMul (a1, (EAdd (a2, b1))) |
EAdd (EMul (a1, a2), EMul (b1, b2)) when a2 = b1 ->
    EMul (a2, (EAdd (a1, b2))) |
EAdd (EMul (a1, a2), EMul (b1, b2)) when a2 = b2 ->
    EMul (a2, (EAdd (a1, b1))) |
e -> e;;

(*
Write the reverse transformation of factorize, expand : exp -> exp, which turns
an expression of the shape a * (b + c) into a * b + a * c.
*)

let expand expression = match expression with
EMul (a, EAdd (x, y)) -> EAdd (EMul (a, x), EMul (a, y)) |
e -> e;;


(*
Implement a function simplify: exp -> exp which takes an expression e and:
    If e is of the shape e * 0 or 0 * e, returns the expression 0.
    If e is of the shape e * 1 or 1 * e, returns the expression e.
    If e is of the shape e + 0 or 0 + e, returns the expression e.
and does nothing otherwise.
*)

let rec simplify expression = match expression with
EAdd (a, b) -> (match simplify a, simplify b with
    (EInt 0, s) | (s, EInt 0) -> s |
    (sa, sb) -> EAdd (sa, sb)) |
EMul (a, b) -> (match simplify a, simplify b with
    (EInt 0, _) | (_, EInt 0) -> EInt 0 |
    (EInt 1, s) | (s, EInt 1) -> s |
    (sa, sb) -> EMul (sa, sb)) |
    EInt x -> EInt x;;
#untrace_all;;
#trace simplify;;


(*
works
*)
simplify
  (EMul
    (EMul (EAdd (EMul (EInt (-1), EInt 1), EInt (-4)),
      EAdd (EInt (-2), EInt (-2))),
    EInt 0));;

(*
fails
*)
simplify
  (EMul (EAdd (EInt 9, EMul (EInt 1, EMul (EInt 0, EInt 8))),
    EAdd (EMul (EInt (-9), EAdd (EInt (-3), EInt 2)), EInt 1)));;

simplify (EInt 0);;

(*
simpler failure
*)
simplify
(EMul
(
(EMul ((EInt 0), (EInt 2))),
(EMul ((EInt 0), (EInt 2)))
)
)
;;