Вставка в Trie с OCaml Функциональное программирование

Question

OCaml Начинающий здесь.

У меня есть с подписью синтаксического дерева

type ('k, 'v) trie = Trie of 'v option * (('k * ('k, 'v) trie) list) 

Мне нужен способ вставки ниже, но я невежествен. Каков наилучший подход к реализации этого с OCaml (стандартные библиотеки в порядке)? Должен ли я переписывать три или массив внутри? Если это так, как я это делаю с OCaml ?:

val insert : ('k, 'v) trie -> 'k list -> 'v -> ('k, 'v) trie 
insert t ks v returns a new trie that is the same as t, but ks is mapped to v. 

Вот примеры попыток с отображениями:

(* maps ['a'] to 1 *) 
Trie (None, ['a', Trie (Some 1, [])]) 

(* maps [] to 1, ['a'] to 2, ['a'; 'b'] to 3 and ['a'; 'c'] to 4 *) 
    Trie (Some 1, ['a', Trie (Some 2, ['b', Trie (Some 3, []); 'c', Trie (Some 4, [])])]) 

Answer 1

Это не имеет никакого смысла говорить «рекурсии над синтаксического дерева» по крайней мере, не для меня.

Очевидная возможность рекурсии - это когда есть внутренняя структура того же типа, что и содержащая структура. Например, ваше определение trie содержит список (ключ, trie) внутри него. Разумеется, ваша рекурсия будет включать в себя подбор подходящей одной из этих внутренних пар и рекурсивный вызов, включающий его trie.

Update

Некоторые ответы на новые комментарии/вопросы.

Я собираюсь предположить, что вы сохраняете список пар, отсортированный по ключу. Вам определенно нужно проверить, есть ли ключ или нет. По сути, это не отличается от добавления нового элемента в отсортированный список.

(Если вы не держать список отсортирован, вы должны проверить, есть ли там ключ, и если не добавить новый ключ с самого начала. Это не сильно отличается, по большому счету.)

Списки OCaml являются неизменяемыми, поэтому вы не можете добавить элемент в список. Вместо этого вы возвращаете новый список, в котором есть все старые элементы, а также новый. Старый список не изменен в процессе (будучи неизменным, он не может изменить ).

Я не хочу просто писать код для вас. Но вот функция, которая «добавляет» новый элемент в отсортированный список.

let rec add_to_list l e = 
    match l with 
    | [] -> [e] 
    | h :: t -> if e < h then e :: l else h :: add_to_list t e