足し算・かけ算からなる数式を表す型

まずは型の定義。

```# type arith = Const of int | Add of arith * arith | Mul of arith * arith;;
type arith = Const of int | Add of arith * arith | Mul of arith * arith
```

```# let rec eval = function
Const n -> n
| Add (a, b) -> eval a + eval b
| Mul (a, b) -> eval a * eval b;;
val eval : arith -> int = <fun>
# let rec string_of_arith = function
Const n -> string_of_int n
| Add (a, b) -> "(" ^ string_of_arith a ^ "+" ^ string_of_arith b ^ ")"
| Mul (a, b) -> string_of_arith a ^ "*" ^ string_of_arith b;;
val string_of_arith : arith -> string = <fun>
# let rec expand = function
Mul (a, Add (b, c)) ->
let (a', b', c') = (expand a, expand b, expand c) in
Add (expand (Mul (a', b')), expand (Mul (a', c')))
| Mul (Add (a, b), c) ->
let (a', b', c') = (expand a, expand b, expand c) in
Add (expand (Mul (a', c')), expand (Mul (b', c')))
| a -> a;;
- : arith -> arith = <fun>
```

いろんな式について試してみた。

```# let exp1 = Mul (Add (Const 3, Const 4), Add (Const 2, Const 5));;
val exp1 : arith = Mul (Add (Const 3, Const 4), Add (Const 2, Const 5))
# string_of_arith exp1;;
- : string = "(3+4)*(2+5)"
# eval exp1;;
- : int = 49
# string_of_arith (expand exp1);;
- : string = "((3*2+4*2)+(3*5+4*5))"

# let exp2 = Add (Mul (Const 3, Add (Const 4, Const 5)), Mul (Const 5, Add (Const 3, Const 4)));;
val exp2 : arith =
Mul (Const 5, Add (Const 3, Const 4)))
# string_of_arith exp2;;
- : string = "(3*(4+5)+5*(3+4))"
# eval exp2;;
- : int = 62
# string_of_arith (expand exp2);;
- : string = "((3*4+3*5)+(5*3+5*4))"

# let exp3 = Mul (Add (Mul (Const 3, Const 2), Mul (Const 4, Const 3)),
Add (Mul (Const 2, Const 3),
Add (Mul (Const 1, Const 2), Mul (Const 2, Const 3))));;
val exp3 : arith =
Mul (Add (Mul (Const 3, Const 2), Mul (Const 4, Const 3)),
Add (Mul (Const 2, Const 3),
Add (Mul (Const 1, Const 2), Mul (Const 2, Const 3))))
# string_of_arith exp3;;
- : string = "(3*2+4*3)*(2*3+(1*2+2*3))"
# eval exp3;;
- : int = 252
# string_of_arith (expand exp3);;
- : string = "((3*2*2*3+4*3*2*3)+((3*2*1*2+4*3*1*2)+(3*2*2*3+4*3*2*3)))"
```

```# let rec string_of_arith = function
Const n -> string_of_int n
| Add (a, b) -> string_of_arith a ^ "+" ^ string_of_arith b
| Mul (a, b) ->
let string_of = function
Add _ as c -> "(" ^ string_of_arith c ^ ")"
| c -> string_of_arith c
in
string_of a ^ "*" ^ string_of b;;
val string_of_arith : arith -> string = <fun>
```

かけ算の中身が足し算の時のみ、括弧が付きます。これでOKなはず。

```val string_of_arith : arith -> string = <fun>
# string_of_arith exp1;;
- : string = "(3+4)*(2+5)"
# string_of_arith (expand exp1);;
- : string = "3*2+4*2+3*5+4*5"
# string_of_arith exp2;;
- : string = "3*(4+5)+5*(3+4)"
# string_of_arith (expand exp2);;
- : string = "3*4+3*5+5*3+5*4"
# string_of_arith exp3;;
- : string = "(3*2+4*3)*(2*3+1*2+2*3)"
# string_of_arith (expand exp3);;
- : string = "3*2*2*3+4*3*2*3+3*2*1*2+4*3*1*2+3*2*2*3+4*3*2*3"
val exp4 : arith =
# string_of_arith exp4;;
- : string = "1+2+3+4+5"
# let exp5 = Mul (exp4, Mul (exp4, exp4));;
val exp5 : arith =