Objective Caml 入門 手習い（6章）その3

6章の難関。自分でも自信がない。

• Objective Caml 入門

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]));;

感想

二分木と二分探索木を間違えてて、すごく難しく考えてしまった。