Как вставить список значений в дерево с помощью функции 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 не может вернуть *1005* то, что вы хотите.

Другими словами, List.map полезен только для узкой цели преобразования одного списка в другой на основе простогоПравило, которое применяется отдельно к каждому элементу списка.

Сгибающие функции List.fold_left и List.fold_right, с другой стороны, являются гораздо более общими функциями, которые могут выполнять практически любые требуемые вычисления, с которыми необходимо работатькаждый из элементов списка по очереди.Это ситуация, в которой вы находитесь, поэтому вы должны использовать ее.