haskell - 通用 Trie Haskell 实现

Question

我需要在 Haskell 中实现一个通用的Trie实现，但我找不到。

我实现了自己的功能（这里只有键，我不需要 Trie 上的数据）但我想在 Haskell 中找到一个好的 Trie 实现以供将来使用（我是新手 Haskeller）。

我发现 Data.Trie 但键是 ByteString。

Data.Trie 是正确的选择吗？（然后我不知道如何使用它）

谢谢！！！:D

Answer 1

查看Hackage和GitHub 上的 MemoTrie 包。有关简单而优美的基础理论的背景，请参阅有关记忆化的 Haskell wiki页面，其中包括 Ralf Hinze 的两篇论文，我的一篇，以及一些博客文章。

另一个 trie/memoization 包是 functor-combo，也在Hackage和GitHub 上。这个包体现了优雅记忆中描述的想法的实现，具有高阶类型和其他博客文章。

其他一些相关的包：

• Edward Kmett 的可代表尝试
• Luke Palmer 的数据记忆组合器

Answer 2

应要求从评论中移出...

我知道的唯一非常通用的 trie 实现是list-triespackage。它总是让我觉得有点过度设计，但一个人的“过于复杂”是另一个人的“功能齐全”，所以如果它适合你的目的，那就去吧。此外，该软件包似乎得到了积极的维护，这很好。

哦，由于包没有在我能看到的任何地方明确说明这一点：“Patricia trie”版本是一种将单分支节点序列压缩为存储公共密钥前缀的单个节点的 trie。所以对于键“aabb”和“aabc”，你会得到一个带有“aab”的节点，然后分支“b”和“c”。标准的 trie 总是一次分支一个元素。

Answer 3

http://hackage.haskell.org/package/TrieMap是我当时的一些工作。我并不完全清楚您所说的“通用”是什么意思，但TrieMap支持或多或少的任意（递归，甚至！）代数数据类型，例如二叉树，作为特里键。