如何使用Map函数将值列表插入树？

Question

所以，我有一个定义的树：

type ('k, 'v) avlnode =
  | Leaf
  | Node of int * 'k * 'v * ('k, 'v) avlnode * ('k, 'v) avlnode

以及将值插入给定树的函数。

let rec set (n : ('k, 'v) avlnode) (key : 'k) (value : 'v) : ('k, 'v) avlnode =
  match n with
  | Leaf -> Node (0, key, value, Leaf, Leaf)
  | Node (h, k, v, left, right) ->
      if k = key then Node (h, k, value, left, right)
      else if key < k then Node (h, k, v, set left key value, right)
else Node (h, k, v, left, set right key value)

我要做的是编写一个函数，使用Map向树中插入值列表。我现在拥有的是这段代码。

let add_all (n : ('k, 'v) avlnode) (keys : ('k * 'v) list) : ('k, 'v) avlnode =
  let new_set (key : 'k * 'v) : ('k, 'v) avlnode = set n (fst key) (snd key) in
  let mutated_nodes = List.map new_set keys in
  match List.tl mutated_nodes with [] -> Leaf | f :: l -> f

该函数的问题是它将每个值插入到初始树而不是新的变异树。我如何编写这个函数，以便让我有一个包含列表中所有值的树？

Answer 1

只是详细说明@Lee的评论：

List.map的类型是：('a -> 'b) -> 'a list -> 'b list。仅从类型中就可以看出它只能返回一个值列表。输出列表中的每个值都是将函数应用于输入列表中的某个值的结果。 List.map没有办法归还树，这就是你想要的。

换句话说，List.map仅用于根据一个简单的规则将一个列表转换为另一个列表的狭隘目的，该规则单独应用于列表的每个元素。

另一方面，折叠函数List.fold_left和List.fold_right是更通用的函数，它们可以执行几乎任何需要依次处理列表的每个元素的所需计算。这就是你所处的情况，所以你应该使用它。