1

私は次の種類の木を持っています

type 'a tree = 
    | Leaf of 'a
    | Node of 'a * ('a tree) * ('a tree);;

また、次のように 2 つの関数 fold_tree と map_tree もあります。

let rec map_tree f t=
    match t with
    | Leaf v -> Leaf (f v)
    | Node(a,lt,rt) -> Node(f a,map_tree f lt, map_tree f rt);;

let rec fold_tree f1 f2 t =
    match t with
    | Leaf v -> f1 v
    | Node(a,lt,rt) -> f2 a (fold_tree f1 f2 lt) (fold_tree f1 f2 rt);;

fold_tree を使用して map_tree を実装することは可能ですか?

4

2 に答える 2

3 
let map_by_fold f t = 
   let f1 x = Leaf (f x) in
   let f2 x l r = Node (f x, l, r) in
   fold_tree f1 f2 t;;

例：

# let a = Node(10, Node (2, (Leaf 1), (Leaf 4)), Leaf 8);;
val a : int tree = Node (10, Node (2, Leaf 1, Leaf 4), Leaf 8)

# map_by_fold (fun x->2*x) a;;
- : int tree = Node (20, Node (4, Leaf 2, Leaf 8), Leaf 16)
于 2013-09-13T05:21:53.790 に答える
3

これは宿題の問題のような趣があり、与えられたのは問題のステートメントだけです。はい/いいえで答えたり、その方法を示したりするだけでは役に立ちません (可能な場合)。しかし、これについては次のように考えることができるかもしれません。マップは、各部分が特定の機能によって処理されたもののコピーを作成します。折り畳みは、整然とした形で何かのすべての部分をトラバースしながら、任意の結果を作成します。任意の結果は、変更された部分を含むコピーになる可能性がありますか?

より良いヘルプを得るには、独自の推論やコードなどを示す必要があります。

于 2013-09-13T05:25:21.273 に答える