rose-trie: Provides "Data.Tree.RoseTrie": trees with polymorphic paths to nodes, combining properties of Rose Tree data structures and Trie data structures.
A rose tree is a tree of trees, where every node contains a leaf and set of sub-trees. A trie is a tree structure where each node can be accessed using a "path," where a path is a list of keys. A rose-trie does both. RoseTries are best used in situations where every leaf in the Trie needs to accessible by a list of polymorphic path elements.
The underlying implementation is based on Data.Map, from the Haskell
Platform's "containers" package. So unlike the ordinary rose tree, where each
node contains a list of sub-trees, the RoseTrie contains a Map of sub-trees,
where each key in the Map forms a single link in the trie path. As a result, the
path for the RoseTrie is a list data type that is polymorphic over list elements
which instantiate both the
Prelude.Eq type classes.
Operating on a RoseTrie with a path of length
p performs up to
p times a
O(log n) Map operations on each of the sub-tree Map structures
n elements, therefore path lookups and insertions in a RoseTrie
data structure are on the order of
O(p * log n) time complexity.
This library was originally part of the Dao package, but has been branched into it's own package in the hopes that it will be useful in a wider variety of projects.
|Versions [RSS]||0.1.0.0, 220.127.116.11, 18.104.22.168, 22.214.171.124, 126.96.36.199, 188.8.131.52, 184.108.40.206|
|Dependencies||base (>=4.7 && <4.8), containers (>=0.5.5.0 && <=0.5.5.1), deepseq (>=220.127.116.11 && <=18.104.22.168), minilens (==22.214.171.124), mtl (>=2.2.0 && <=2.2.1), transformers (>=0.3.0.0 && <=0.4.3.0) [details]|
|Copyright||2008-2015 Ramin Honary|
|Uploaded||by RaminHonary at 2016-02-19T19:01:27Z|
|Downloads||4136 total (6 in the last 30 days)|
|Rating||(no votes yet) [estimated by Bayesian average]|
|Status||Docs uploaded by user [build log]
All reported builds failed as of 2016-02-19 [all 1 reports]