map_tree and fold_tree in ocaml

Question

I have the following type of tree

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

and I also have 2 function fold_tree and map_tree as follows:

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

Is it possible to implement map_tree using fold_tree?

Answer 1

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

Example:

# 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)

Answer 2

This has the flavor of a homework problem, and all you've given is the statement of the problem. It doesn't seem helpful just to give a yes/no answer, or to show how to do it (if it's possible). But maybe you can think about this as follows. A map creates a copy of something where each part has been processed by a certain function. A fold creates an arbitrary result while traversing all the parts of something in an orderly fasion. Could an arbitrary result be a copy with modified parts?

To get better help you should show some of your own reasoning, code, etc.