Tiger book 一章

(define -ayalog ’())に良い刺激を受けて、ずっと積ん読になっていた最新コンパイラ構成技法を読み始めました。以前読んだときは、最初の練習問題で転んでいたのですが、右手に実践F#、左手にPurly Functional Data Structureで突破できました。関係無いのですが、F# 3.0に対応した日本語の本が欲しいです。

練習問題1.1

2分木の操作の問題。2分木に項目があるかどうかを調べるmember関数、2分木に項目を追加するinsert関数、キーから束縛へ写像するloopup関数の実装。コンパイラで使うシンボルテーブルで使うらしい。

// Tiger book exercise 1.1
// Refer to Purly Functional Data Structure
type Tree<'Key, 'T> =
  | Empty
  | Node of 'Key * 'T * Tree<'Key, 'T> * Tree<'Key, 'T>

let rec tree_member tree key =
  match tree with
    | Empty -> false
    | Node(k, v, left, right) ->
        match key with
          | _ when k > key -> tree_member left key
          | _ when k < key -> tree_member right key
          | _ -> true    //k = key


let rec insert tree new_key new_value =
  match tree with
    | Empty -> Node(new_key, new_value, Empty, Empty)
    | Node (k, v, left, right) ->
      match v with
        | _ when new_key < k -> Node(k, v, (insert left new_key new_value) , right)
        | _ when new_key > k -> Node(k, v, left, (insert right new_key new_value))
        | _ -> Node(new_key, new_value, left, right)

let rec lookup tree key =
  match tree with
    | Empty -> None
    | Node(k, v, left, right) ->
        match key with
          | _ when k > key -> lookup left key
          | _ when k < key -> lookup right key
          | _ -> Some v 
       
let xs = Node('d', "d_value",
              Node('b', "b_value",
                   Node('a', "a_value", Empty, Empty),
                   Node('c', "c_value", Empty, Empty)),
              Node('g', "g_value",
                   Node('f', "f_value", Empty, Empty),
                   Node('h', "h_value", Empty, Empty)))


// member test
List.iter (fun k -> printf "%c : %b\n" k (tree_member xs k)) ['a'..'i']
printfn ""

// insert test
let xs1 = insert xs 'e' "e_value"
List.iter (fun k -> printf "%c : %b\n" k (tree_member xs1 k)) ['a'..'i']
printfn ""

// lookup test
List.iter (fun k ->
           let result = lookup xs k 
           match result with
           | Some n -> printf "%c : %s\n" k n
           | None -> printf "%c : None\n" k
           ) ['a'..'i']
printfn ""

// d. (a) insert t s p i p f b s t
let root_a = Node('t', "", Empty, Empty)
let tree_a = insert root_a 's' ""
           |> (fun t -> insert t 'p' "")
           |> (fun t -> insert t 'i' "")
           |> (fun t -> insert t 'p' "")
           |> (fun t -> insert t 'f' "")
           |> (fun t -> insert t 'b' "")
           |> (fun t -> insert t 's' "")
           |> (fun t -> insert t 't' "")

printf "%A\n" tree_a

// d. (b) insert a b c d e f g h i
let root_b = Node('a', "", Empty, Empty)
let tree_b = insert root_b 'b' ""
           |> (fun t -> insert t 'c' "")
           |> (fun t -> insert t 'd' "")
           |> (fun t -> insert t 'e' "")
           |> (fun t -> insert t 'f' "")
           |> (fun t -> insert t 'g' "")
           |> (fun t -> insert t 'h' "")
           |> (fun t -> insert t 'i' "")

printf "%A\n" tree_b