通用Trie Haskell实现

Question

我需要Haskell中的通用Trie实现,但我找不到任何.

我实现了自己的功能(这里只有键,我不需要Trie上的数据)但是我想在Haskell中找到一个好的Trie实现以供将来使用(我是菜鸟新手).

我找到了Data.Trie,但键是ByteString.

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

谢谢!!!:d

Answer 1

查看Hackage和GitHub 上的MemoTrie包.有关简单而美观的基础理论的背景知识,请参阅Haskell wiki 页面上的memoization,包括Ralf Hinze的两篇论文,一篇由我发表的文章和一些博客文章.

另一个trie/memoization包是functor-combo,也是Hackage和GitHub上的.此软件包包含使用高阶类型和其他博客文章在Elegant memoization中描述的创意实现.

其他一些相关的包:

@josejuan:"memoized structure"*是*trie.记忆是两个阶段的组合:`memo = untrie.trie`.第一阶段(`trie`)将函数转换为trie,第二阶段将trie转换回函数.如果你想要的只是memoization,你可以将`memo`视为黑盒子.如果你想更多地检查和转换数据本身,只需在`trie`之后和`untrie`之前进行调解.这些特里结构总是在"Functor","Applicative","Foldable","Traversable"和"Monad"中,因此可以立即使用很多功能来操作它们. (2认同)

Answer 2

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

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

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