6章の難関。自分でも自信がない。
Exercise 7
問題
数式の文字列表現を求める関数 string_of_arith, 分配則を用いて 数式を (i11 … i1n1) + … + (im1 … imnm) の形に変形する関数 expand を定義せよ.
自分の答え
type arith = | Const of int | Add of arith * arith | Mul of arith * arith ;; let exp = Mul (Add (Const 3, Const 4), Add (Const 2, Const 5));; let rec string_of_arith = function | Const n -> string_of_int n | Add (m, n) -> "(" ^ (string_of_arith m) ^ "+" ^ (string_of_arith n) ^ ")" | Mul (m, n) -> "(" ^ (string_of_arith m) ^ "*" ^ (string_of_arith n) ^ ")" ;; let rec expand = function | Const n -> Const n | Add (m, n) -> Add (expand m, expand n) | Mul (Add (m, n), Add (m', n')) -> Add (Add (expand (Mul (m, m')), expand (Mul (m, n'))), Add (expand (Mul (n, m')), expand (Mul (n, n')))) | Mul (m, n) -> Mul (expand m, expand n) ;;
Exercise 8
問題
Exercise8 1, 2, 3, 4 からなる可能な二分探索木の形を列挙し,それぞれの形を作るためには 空の木から始めて,どの順番で要素を add していけばよいか示せ.
自分の答え
let labels = [1; 2; 3; 4];; let create_tree l = let rec create_tree ret l = let rec add t x = match t with | Lf -> Br (x, Lf, Lf) | Br (y, left, right) -> match y with | y when y = x -> Br (y, left, right) | y when y < x -> Br (y, left, add right x) | _ -> Br (y, add left x, right) in match l with | [] -> ret | x::xs -> create_tree (add ret x) xs in create_tree Lf l ;; let permutation l = let rec perm n xs a b = let remove x xs = List.filter (fun y -> x <> y) xs in if n = 0 then a::b else List.fold_right (fun x y -> perm (n-1) (remove x xs) (x::a) y) xs b in perm (List.length l) l [] [] ;; let del_dup l = let rec del_dup rst = function | [] -> rst | x::xs -> del_dup (x :: List.filter (fun y -> y <> x) rst) xs in del_dup l l ;; del_dup (map create_tree (permutation [1;2;3;4]));;
感想
二分木と二分探索木を間違えてて、すごく難しく考えてしまった。