Prefix trie‘s are cool data structures that let you compress a dictionary of words based on their shared prefix. If you think about it, this makes a lot of sense. Why store
abysmal when you only need to store
a,b,b,r,s,y,s,m,a,l. Only storing what you have to (based on prefix) in this example gives you a 70% compression ratio! Not too bad, and it would only get better the more words you added.
The classical way of dealing with prefix tries is to store the suffixes using a map, but for fun I tried something different and used a list.
The main data structure I had was like this
type Key a = [a] data Trie key = Node (Maybe key) [Trie key] Bool deriving (Show, Eq, Read)
So a trie is really just a node that has a list of other tries … Read more