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
再帰的な定義は、非常に簡潔でわかりやすく、実行速度も速い。しかし、メモリ消費量が大
末尾再帰的な定義は、簡潔ではなく、実行速度も遅い。しかし、メモリ消費量が小
Labels: F# FSharp