在 Ocaml 中插入一个 trie 的实现

Question

我不知道如何更改我的 add 函数的代码。

type trie = Node of bool * (char * trie) list 

let explode word = 
       let rec explode' i acc = 
           if i < 0 then acc else explode' (i-1) (word.[i] :: acc) 
            in explode' (String.length word - 1) []

let rec exists w tr = match w, tr with
    | [], Node (b, _) -> b
    | h::t, Node (_, l) -> try exists t (List.assoc h l) with Not_found -> false

let rec add w tr = match w, tr with 
    | [], Node (_, l) -> Node (true, l)
    | h :: t, Node (b, l) -> try add t (List.assoc h l)   
                             with Not_found -> Node (false, (h, add t tr) :: l)

问题是当 List.assoc h l 找到一些东西时，我没有跟踪我的结构，在递归调用期间没有构建 Node 所以我丢失了数据。

示例：

# let empty = Node(true, []);;
 - : trie = Node (true, [])
# let w = explode "hi";;
val w : char list = ['h'; 'i']
# let ww = explode "hit";;
val ww : char list = ['h'; 'i'; 't']
# let tr = add w x;;
val tr : trie = Node (false, [('h', Node (false, [('i', Node (true, []))]))])
# add ww tr;;
- : trie = Node (false, [('t', Node (true, []))])

Answer 1

看来您的基本计划是通过 List.assoc 研究数据结构，然后在找到合适的位置时添加新节点。如果您可以修改结构，这是有道理的。但是，您的数据结构是不可变的。对于不可变数据，您的基本计划必须是构建 new 数据结构，而不是修改旧数据结构。所以你必须想象自己找到正确的位置，同时沿途跟踪旧结构，然后从该位置开始构建新结构。

这里有一些代码可以保存一个关联列表，该列表计算到目前为止看到的字符实例的数量。请注意，它 returns 一个新的关联列表而不是修改旧的（这是不可能的）：

 let rec add_char_count list char =
     match list with
     | [] -> [(char, 1)]
     | (hchar, hcount) :: t -> 
         if hchar = char then (hchar, hcount + 1) :: t
         else (hchar, hcount) :: add_char_count t char

递归调用(hchar, hcount) :: add_char_count t char是记忆旧结构的地方。它从添加新字符之前的列表部分重建旧结构。

在 Ocaml 中插入一个 trie 的实现

Insert implementation for a trie in Ocaml

ocaml

trie