[F#] 二分木(binary tree)専用のmap関数

Memo : Node(左の木, このノードの値, 右の木)

type 'a tree = Nil | Node of ('a tree) * 'a * ('a tree)
再帰的：　（通りがけ順, 中置記法）
let rec map0 f t =
  match t with
    Nil -> Nil
  | Node(l,v,r) -> let v' = f v in Node(map0 f l, v', map0 f r)
末尾再帰的：　（帰りがけ順, 逆ポーランド記法）
let map3 f tree =
   let rec map' subtree build =
       match subtree with
           | Nil -> build Nil
           | Node(l, v, r) ->
               let v' = f v in
               map' l (fun l' -> map' r (fun r' -> Node(l', v', r') |> build)) in
   map' tree (fun x -> x)

テスト用コード：
// 関数のリスト
let maps : (string * (('a->'b) -> 'a tree -> 'b tree)) list = 
   [
    "map0 (non-tail-recursive):", map0;
    "map3 (Vladimir's functional):", map3;  
   ]

// 木の表示
let rec print_tree t = match t with
  Nil -> printf ""
| Node(l,v,r) ->
    printf "(";
    print_tree l; 
    printf "%d" v;
    print_tree r;
    printf ")"
;;

// テスト用の木の用意と、関数のリストに登録されている関数の実行、そして木の表示
let _ =
  let tree = Node(Node(Node(Nil,1,Nil),2,Node(Nil,3,Nil)),5,Node(Node(Nil,6,Nil),7,Node(Nil,8,Nil))) in
  print_tree tree; printf "\n";
  List.iter (fun (s,map) -> print_tree (map (fun x -> x+1) tree); printf "\n") maps
;;
テスト用の木構造


結果：
(((1)2(3))5((6)7(8)))  -- テスト用の木
(((2)3(4))6((7)8(9)))  -- 関数適用後の木 -- map0
(((2)3(4))6((7)8(9)))  -- 関数適用後の木 -- map3
再帰的な定義は、非常に簡潔でわかりやすく、実行速度も速い。しかし、メモリ消費量が大
末尾再帰的な定義は、簡潔ではなく、実行速度も遅い。しかし、メモリ消費量が小