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

Pincers

There's no way to write a trie that works on arbitrary key types. What keys do you want to use? Note that Data.IntMap and Data.IntSet are tries with Int keys. – Burette

C.A. McCann, a Trie only need a type supporting Equality operator over a sequenced source data. With that, you can construct a Trie. What does matter if you don't know underlying type?. Is not my implementation a Trie? Thank you! (But suppose the key type is [a]) – Pincers

Right, you need the keys to either be some sort of sequence or something you can turn into a sequence. For example, Data.IntMap treats an Int as a sequence of bits. Being able to sort or index directly on each chunk is nice, but a list of things you can compare for equality is enough. Anyway, there's a package list-tries out there but it always struck me as a bit confusing. – Burette

Ok (excuse me, sometimes I'm incomprehensible :( ). Thank you!!! – Pincers

Wow! I'm happy, my own Trie implementation follow list-tries package strategy (I was walking right way) :D :D :D Thanks (can you write a response to vote as solved?) :) – Pincers

@C.A.McCann There's nothing inherently problematic with defining tries over near-arbitrary key types. See for example this paper: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.1.6342 AFAIK, the idea is used in Conal's MemoTrie package, but for the specific purpose of memoization. – Fyn

@kosmikus: Of course, but emphasis on "near". You don't need much, but a trie that's completely polymorphic with no class constraint isn't going to happen. – Burette

Answer 1

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.

Burette

Answer 2

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

Supplant

Thank you Conal but I can't map your response into my question (my fault, I'm sure). Intuitively I can't understand how I can inspect (inside) a memoized structure, on the other hand, using trie, I can inspect that structure to produce new information (memoization run as a black box). I read your post frecuently but is too hard (like magic) to me :D :D Thank you anyway!!!! – Pincers

@josejuan: The "memoized structure" is the trie. Memoization is a composition of two phases: memo = untrie . trie. The first phase (trie) converts a function into a trie, and the second phase converts that trie back into a function. If all you want is memoization, you can treat memo as a black box. If you want more inspect and transform the data itself, just intercede after trie and before untrie. These trie structures are always in Functor, Applicative, Foldable, Traversable, and Monad, so there's a lot of functionality immediately available to operate on them. – Supplant

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.

Valona

Very interesting, thank you! list-tries is direct to use and as "generic trie" can be used from any other structure (eg. a tree is traversable/sequentiable then, you can use it with list-tries, another one, you can transform a IntTrie to list-trie [Bit]), but your implementation do it explicitly! (I saw your package but I did not realize), I will use in future, sure! :D Thank you! – Pincers