f# - F# 中的不可变 Trie 结构

Question

我正在使用 aho-corasick 算法来尝试使用 F# 做得更好一些，但我遇到了 Trie 实现的问题，它们都是可变的或者不能进行尾调用优化。

我所看到的基本问题是，必须“自下而上”构建不可变数据结构，因为您无法更改它们指向的内容，因此您的选择是使它们可变，或者在进行过程中找出节点（即构造中的递归）。

有什么方法可以在构造上通过尾调用优化来制作不可变的 trie 数据结构？（并且不会因复制而降低效率。）

Answer 1

尾调用优化可以通过使用延续来消除。这是一个示例，其中键和值string分别int为

type Trie = 
 | Data of string * int * Trie * Trie 
 | Leaf 

let Insert start key value = 
  let rec inner current withNode = 
    match current with
    | Data (currentKey, currentValue, left, right) ->
      if key < currentKey then
        inner left (fun left -> Data (currentKey, currentValue, left, right))
      else 
        inner right (fun right -> Data (currentKey, currentValue, left, right))
    | Leaf -> withNode (Data (key, value, Leaf, Leaf))
  inner start (fun x -> x)

如果您想坚持使用不可变结构，则消除副本会有些困难

Answer 2

我在研究我在不可变特里实现的代码审查帖子时遇到了这篇文章。

使用地图作为链接而不是二叉树是高效的。