不可变的Trie结构在F#中

Question

我正在尝试使用Aho-Corasick算法，以提高F#的技能水平。我发现Trie实现存在问题，它们都是可变的或不能进行尾调用优化。

从我所看到的基本问题来看，不可变数据结构必须从“底部向上”构建，因为您无法更改它们所指向的内容，因此您的选择要么使它们可变，要么在构建过程中找出节点（即在构造函数中递归）。

是否有任何方法可以使用尾调用优化构建不可变的Trie数据结构？（并且不通过复制而失去效率。）

- Snark

Answer 1

尾调用优化可以通过使用 continuation 来消除。以下是一个示例，其中键和值分别为 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)

消除副本如果你想坚持使用不可变结构会更加困难。

- JaredPar

---

啊，延续，我发现这些让我头疼，所以我想多练习一下，谢谢。消除复制是可能的吗？看到你在这里做的，我意识到它并不像我想象的那么重要（复制的数据比我想象的少），但出于原则等方面，我很好奇。 - Snark

@user442859 是的，继续函数需要一段时间才能习惯。我认为我个人的成就是，我能够在只有一个小语法错误的情况下完成这个任务。我相信在许多情况下都有消除复制的方法，但对于像这样的树形结构，我个人不知道一个好的方法。 - JaredPar

Answer 2

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

它使用映射而不是二叉树作为链接，因此具有较高的性能。

- psaxton