当前位置：文江博客话题详情

F# 中的不可变 Trie 结构

发布于 2024-10-26 11:10:23 字数 233 浏览 4 评论 0原文

我正在尝试使用 aho-corasick 算法来尝试使用 F# 来改进一点，并且我遇到了 Trie 实现的问题，它们都是可变的或者无法进行尾部调用优化。

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

有没有办法制作一个不可变的 trie 数据结构，并在构造上进行尾调用优化？（并且不会因复制而损失效率。）

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

一腔孤↑勇 2024-11-02 11:10:23

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

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

The tail call optimiation can be eliminated by using a continuation. Here's a sample where the key and value are string and int respectively

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)

Eliminating the copies is a bit more difficult if you want to stick with immutable structures

回复收藏 0 原文