1sealed trait Expr
2case class Num(value: Double) extends Expr
3case class Add(left: Expr, right: Expr) extends Expr
4case class Mul(left: Expr, right: Expr) extends Expr
5case class Var(name: String) extends Expr
6case class Let(name: String, value: Expr, body: Expr) extends Expr
7
8object Evaluator {
9 type Env = Map[String, Double]
10
11 def eval(expr: Expr, env: Env = Map.empty): Double =
12 expr match {
13 case Num(v) => v
14 case Add(l, r) => eval(l, env) + eval(r, env)
15 case Mul(l, r) => eval(l, env) * eval(r, env)
16 case Var(name) => env.getOrElse(name,
17 throw new RuntimeException(
18 s"Undefined variable: $name"
19 ))
20 case Let(name, value, body) =>
21 val v = eval(value, env)
22 eval(body, env + (name -> v))
23 }
24
25 def simplify(expr: Expr): Expr = expr match {
26 case Add(Num(0), r) => simplify(r)
27 case Add(l, Num(0)) => simplify(l)
28 case Mul(Num(1), r) => simplify(r)
29 case Mul(l, Num(1)) => simplify(l)
30 case Mul(Num(0), _) => Num(0)
31 case Mul(_, Num(0)) => Num(0)
32 case Add(l, r) => Add(simplify(l), simplify(r))
33 case Mul(l, r) => Mul(simplify(l), simplify(r))
34 case other => other
35 }
36
37 def variables(expr: Expr): Set[String] = expr match {
38 case Num(_) => Set.empty
39 case Var(name) => Set(name)
40 case Add(l, r) => variables(l) ++ variables(r)
41 case Mul(l, r) => variables(l) ++ variables(r)
42 case Let(n, v, b) => variables(v) ++ (variables(b) - n)
43 }
44
45 def substitute(
46 expr: Expr,
47 name: String,
48 replacement: Expr
49 ): Expr = expr match {
50 case Var(n) if n == name => replacement
51 case Add(l, r) =>
52 Add(substitute(l, name, replacement),
53 substitute(r, name, replacement))
54 case Mul(l, r) =>
55 Mul(substitute(l, name, replacement),
56 substitute(r, name, replacement))
57 case other => other
58 }
59}