# The rose-trie package

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.Ord` and `Prelude.Eq` type classes.

Operating on a RoseTrie with a path of length `p` performs up to `p` times a
number of `O(log n)` Map operations on each of the sub-tree Map structures
containing `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.

## Properties

Versions | 0.1.0.0, 1.0.0.0, 1.0.0.1, 1.0.0.2, 1.0.0.3, 1.0.0.4, 1.0.0.5 |
---|---|

Dependencies | base (>=4.7 && <4.9), containers (>=0.5.5.0 && <0.7.0.0), deepseq (>=1.2.0.0 && <1.5.0.0), minilens (>=1.0.0.1 && <=2.0.0.0), mtl (>=2.2.0 && <=2.2.1), transformers (>=0.3.0.0 && <=0.4.3.0) [details] |

License | GPL-3 |

Copyright | 2008-2016 Ramin Honary |

Author | Ramin Honary |

Maintainer | ramin.honary@gmail.com |

Category | Data |

Home page | https://github.com/RaminHAL9001/rose-trie |

Uploaded | Mon Mar 27 08:27:22 UTC 2017 by RaminHonary |

Distributions | NixOS:1.0.0.5 |

Downloads | 328 total (24 in the last 30 days) |

Votes | |

Status | Docs uploaded by user [build log] All reported builds failed as of 2017-03-27 [all 3 reports] Hackage Matrix CI |

## Downloads

- rose-trie-1.0.0.5.tar.gz [browse] (Cabal source package)
- Package description (included in the package)