Ocaml将'树变为'b树

Question

我已经定义了

type 'a tree =
| Tree of 'a tree * 'a * 'a tree
| Leaf of 'a
| Null;;

现在我必须定义一个将整体'a tree改为的函数'b tree.

我在谷歌上搜索并试图自己解决它,但我被困了.有小费吗？

Answer 1

一种可能性是map功能类似于树木.例如:

let rec treemap f t = match t with
    Null           -> Null
 |  Leaf x         -> Leaf (f x)
 |  Tree (l, x, r) -> Tree (treemap f l, f x, treemap f r)

在这里t : 'a tree,f : 'a -> 'b和treemap : 'a tree -> ('a -> 'b) -> 'b tree,它产生'b tree所需的.

这是制作这样一个函数的最"自然"方式:你有一个具有类型值的树'a,并且你想获得一个具有类型值的新树'b- 所以你只需要一个树和一些映射值的方法一种类型到另一种的价值.

我认为值得指出的是,这不是唯一的此类功能.你可以创建一个函数treereplace : 'a tree -> 'b -> 'b tree,它只创建一个结构相同的树,但用给定的一个替换每个值,或者一个函数执行相同但翻转每个Tree节点的左/右分支.有无数的功能可以制作'a tree和制作'b tree你可以制作的,上面只是可以说是最自然和最有用的.

编辑:改进/评论欢迎 - 我不知道OCaml,我从对SML的理解中共同攻击了这个例子.