f# - 是否有人拥有或知道 F# 中可用的持久前缀树？

Question

对于我的特定应用程序，F# 的 Map 和 Set 的性能相当欠缺。似乎一个不错的前缀特里树会大大提高我的解释器的性能，尤其是在按名称查找符号方面。唯一需要注意的是，它必须对添加和查找操作非常有效（尤其是当键是字符串时），并且对于持久性是不可变的（意味着非破坏性更新）。

如果没有这样的野兽可用，OCaml 或 Haskell 的参考实现将帮助我开始使用。

非常感谢！

Answer 1

要关闭此线程（请参阅问题评论）：

Haskell 实现

OCaml 实现

Answer 2

似乎一个不错的前缀特里树会大大提高我的解释器的性能，尤其是在按名称查找符号方面。唯一需要注意的是，它必须对添加和查找操作非常有效（尤其是当键是字符串时），并且对于持久性是不可变的（意味着非破坏性更新）。

您的限定词“高效”和“持久不变”是相互排斥的。持久性数据结构（通常）本质上非常低效，通常比命令式数据结构慢 10 倍以上。

如果您想要一个带有符号键的快速字典，那么您需要一个符号表。您的公共 API 使用符号作为字符串，但这些在内部通过哈希表转换为小的正整数并返回。然后可以将带有符号作为键的字典表示为由用于表示符号的整数索引的数组。

我在这里发表了一篇关于符号表的文章。

Answer 3

所以，我只是从 OCaml 移植了一个。不幸的是，它在 tryFind 方面的运行速度比标准 Map 慢。我在这个线程中问为什么 -为什么我的 Trie 查找比标准 F# Map 的慢？

这是代码 -

[<RequireQualifiedAccess>]
module Trie

type Node<'k, 'v when 'k : comparison> =
    { TrieMap : Map<'k, Node<'k, 'v>>
      TrieKvp : ('k list * 'v) option }
    member inline x.IsEmpty = x.TrieKvp.IsNone && x.TrieMap.IsEmpty

let inline make map kvp =
    { TrieMap = map
      TrieKvp = kvp }

let inline makeEmpty () : Node<'k, 'v> = make Map.empty None

let inline isEmpty (node : Node<'k, 'v>) = node.IsEmpty

let rec tryFind (key : 'k list) node =
    match key with
    | [] ->
        match node.TrieKvp with
        | Some (_, value) -> Some value
        | None -> None
    | keyHead :: keyTail ->
        let optSubNode = Map.tryFind keyHead node.TrieMap
        match optSubNode with
        | Some subNode -> tryFind keyTail subNode
        | None -> None

let inline containsKey key node =
    (tryFind key node).IsSome

let rec addInternal (key : 'k list) value node =
    match key with
    | [] -> make node.TrieMap (Some (key, value))
    | keyHead :: keyTail ->
        let newTrie =
            match Map.tryFind keyHead node.TrieMap with
            | Some subTrie -> subTrie
            | None -> makeEmpty ()
        let newTrie2 = addInternal keyTail value newTrie
        make (Map.add keyHead newTrie2 node.TrieMap) node.TrieKvp

let inline add key value node =
    addInternal key value node

let rec addMany kvps node =
    if Seq.isEmpty kvps then node
    else
        let kvpHead = Seq.head kvps
        let kvpTail = Seq.skip 1 kvps
        let newTrie = add (fst kvpHead) (snd kvpHead) node
        addMany kvpTail newTrie

let inline ofList kvps =
    addMany kvps (makeEmpty ())

let inline ofListBy by kvps =
    let pairs = List.map by kvps
    ofList pairs

let rec foldInternal folder rev node state =
    match node.TrieKvp with
    | Some (_, value) -> folder (Map.fold (fun state key value -> foldInternal folder (key :: rev) value state) state node.TrieMap) (List.rev rev) value
    | None -> Map.fold (fun state key value -> foldInternal folder (key :: rev) value state) state node.TrieMap

let inline fold folder state node =
    foldInternal folder [] node state

let rec map (mapper : 'k list -> 'v -> 'a) (node : Node<'k, 'v>) : Node<'k, 'a> =
    match node.TrieKvp with
    | Some (key, value) -> make (Map.map (fun _ value -> map mapper value) node.TrieMap) (Some (key, mapper key value))
    | None -> make (Map.map (fun _ value -> map mapper value) node.TrieMap) None

let inline toValueList node =
    fold (fun state _ value -> value :: state) [] node

let inline singleton (key, value) =
    add key value (makeEmpty ())