-- Initial rose-trie.cabal generated by cabal init. For further
-- documentation, see http://haskell.org/cabal/users-guide/
name: rose-trie
version: 1.0.0.5
synopsis:
Trees with polymorphic paths to nodes, combining properties of Rose Trees and Tries.
description:
.
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.
homepage: https://github.com/RaminHAL9001/rose-trie
license: GPL-3
license-file: LICENSE
author: Ramin Honary
maintainer: ramin.honary@gmail.com
copyright: 2008-2016 Ramin Honary
category: Data
build-type: Simple
cabal-version: >=1.10
library
exposed-modules:
Data.Tree.RoseTrie
default-extensions:
RankNTypes
MultiParamTypeClasses
FlexibleInstances
DeriveDataTypeable
build-depends:
base >=4.7 && <4.9
, containers >=0.5.5.0 && <0.7.0.0
, deepseq >=1.2.0.0 && <1.5.0.0
, mtl >=2.2.0 && <=2.2.1
, minilens >=1.0.0.1 && <=2.0.0.0
, transformers >=0.3.0.0 && <=0.4.3.0
GHC-options: -Wall
-fno-warn-name-shadowing
-fno-warn-unused-do-bind
hs-source-dirs: src
default-language: Haskell2010