使用 OCaml 函数式编程插入 Trie

Question

这里是 OCaml 初学者。

我有一个带有签名的 trie

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

我需要下面的插入方法，但我一无所知。用 OCaml 实现这个的最佳方法是什么（标准库很好）？我应该递归 trie 还是其中的数组？如果是这样，我该如何使用 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

说 "recurse over the trie," 至少对我来说没有任何意义。

一个明显的递归机会是当存在一个与包含结构具有相同类型的内部结构时。例如，您对 trie 的定义中包含一个 (key, trie) 对列表。理所当然的是，您的递归将涉及从这些内部对中选择适当的一对并进行涉及其特里的递归调用。

更新

对新comments/questions的一些回答。

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

（如果你不保持列表排序，你需要检查你的密钥是否存在，如果不存在，则将新密钥添加到开头。大体上没有太大区别。）

OCaml 列表是不可变的，因此您实际上无法将元素添加到列表中。您要做的是 return 一个包含所有旧元素和新元素的新列表。旧列表在此过程中不会更改（不可变，不能更改）。

我不想只为您编写代码。但是这里有一个函数，它 "adds" 一个新元素到一个排序列表。

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

使用 OCaml 函数式编程插入 Trie

Insertion into a Trie with OCaml Functional Programming

functional-programming

ocaml

trie