用OCaml函数编程插入Trie

Question

这里是OCaml初学者。

我有个签名

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

我需要下面的插入方法，但我不知道。用OCaml实现这一点的最佳方法是什么(标准库很好)？我是应该在the上进行递归，还是在其中的数组上进行递归？如果是这样的话，我如何使用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的定义中包含(key，trie)对的列表。这是合理的，您的递归将涉及选择适当的这些内部对之，并作出递归调用涉及其trie。

更新

对新的评论/问题的一些回答。

我假设你把你的配对列表按键排序。您确实需要测试密钥是否已经存在。本质上，这与将新元素添加到排序列表没有什么不同。

(如果您没有对列表进行排序，则需要检查您的密钥是否在那里，如果没有，则将新键添加到开头。从总体上看，这并没有多大区别。)

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