Generic Trie Haskell implementation

Question

I needed a generic Trie implementation in Haskell but I could not find any.

I was implemented my own functions (only keys here, I didn't need data on Trie) but I want to find a good Trie implementation in Haskell for future uses (I'm a rookie haskeller).

I was found Data.Trie but keys are ByteString.

Is Data.Trie the correct option? (and then I don't know how to use it)

Thank you!!! :D

Answer 1

Check out the MemoTrie package on Hackage and on GitHub. For background on the simple & beautiful underlying theory, see the Haskell wiki page on memoization, including two papers by Ralf Hinze, one by me, and some blog posts.

Another trie/memoization package is functor-combo, also on Hackage and on GitHub. This package embodies implementations of ideas described in Elegant memoization with higher-order types and other blog posts.

Some other related packages:

• Edward Kmett's representable-tries
• Luke Palmer's data-memocombinators

Answer 2

Moved from comment by request...

The only very generic trie implementation I know of off the top of my head is the list-tries package. It always struck me as a bit overengineered, but one person's "overcomplicated" is another person's "full-featured", so if it suits your purposes go for it. Also, the package seems to be actively maintained, which is good.

Oh, and since the package didn't state this explicitly anywhere I could see: The "Patricia trie" version is a trie that compresses sequences of single-branch nodes into a single node that stores the common key prefix. So for keys "aabb" and "aabc" you'd get a node with "aab" and then branches "b" and "c". The standard trie always branches one element at a time.

Answer 3

http://hackage.haskell.org/package/TrieMap was some of my work back in the day. It's not fully clear to me what you mean by "generic," but TrieMap supports more-or-less arbitrary (recursive, even!) algebraic data types, e.g. binary trees, as trie keys.