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 回答