(**************************************************************************) (* *) (* Thibaut Balabonski, Sylvain Conchon, Jean-Christophe Filliâtre, *) (* Kim Nguyen, Laurent Sartre *) (* *) (* Informatique - MP2I/MPI - CPGE 1re et 2e années. *) (* Cours et exercices corrigés. Éditions Ellipses, 2022. *) (* *) (* https://www.informatique-mpi.fr/ *) (* *) (**************************************************************************) type expr = | Cst of int | Var | Add of expr * expr | Sub of expr * expr | Mul of expr * expr let rec eval e n = match e with | Cst k -> k | Var -> n | Add (e1, e2) -> eval e1 n + eval e2 n | Sub (e1, e2) -> eval e1 n - eval e2 n | Mul (e1, e2) -> eval e1 n * eval e2 n let rec is_constant e = match e with | Cst _ -> true | Var -> false | Add (e1, e2) | Sub (e1, e2) | Mul (e1, e2) -> is_constant e1 && is_constant e2 let add e1 e2 = match e1, e2 with | Cst k1, Cst k2 -> Cst (k1 + k2) | Cst 0, e | e, Cst 0 -> e | _, _ -> Add (e1, e2) let sub e1 e2 = match e1, e2 with | Cst k1, Cst k2 -> Cst (k1 - k2) | _, Cst 0 -> e1 | _, _ -> Sub (e1, e2) let mul e1 e2 = match e1, e2 with | Cst k1, Cst k2 -> Cst (k1 + k2) | Cst 0, _ | _, Cst 0 -> Cst 0 | Cst 1, e | e, Cst 1 -> e | _, _ -> Mul (e1, e2) let rec simplify e = match e with | Cst _ | Var -> e | Add (e1, e2) -> add (simplify e1) (simplify e2) | Sub (e1, e2) -> sub (simplify e1) (simplify e2) | Mul (e1, e2) -> mul (simplify e1) (simplify e2)