-
Exported names:
-
Imported modules:
Module RW.Trie
A simple trie data structure.
This implementation assumes that the keys are small. It is not (yet) optimized for arbitrary keys. That is, no optimizations are done in regards to memory usage (or access speed) when using different keys with unique prefixes.
Consider a Trie containing the keys a,b,c,aa,ab,ac: root / | \ / | \ a b c / | a b c
This is fine. Now consider a Trie containing the keys a,b,Helloworld root / | \ / | \ a b H | e | l | ... This is an issue because lots of nodes without associated values are created (only the leaf nodes a,b,d have values).
Author: Lasse Züngel
Version: July 2024
Summary of exported operations:
empty
:: Trie a 
An empty trie. |
null
:: Trie a -> Bool
Is the trie empty? |
size
:: Trie a -> Int
Returns the size of the trie. |
singleton
:: Eq a => String -> a -> Trie a
A singleton trie. |
insert
:: Eq a => String -> a -> Trie a -> Trie a
Inserts a value into the trie. |
lookup
:: String -> Trie a -> Maybe a
Looks up a value in the trie. |
fromList
:: Eq a => [(String,a)] -> Trie a
Converts a list of key-value pairs into a trie. |
toList
:: Trie a -> [(String,a)]
Converts a trie into a list of key-value pairs. |
Exported datatypes:
Trie
Trie data structure
Constructors:
Exported operations:
|
An empty trie.
|
|
Returns the size of the trie.
|