Safe Haskell | Safe |
---|---|
Language | Haskell98 |
Data.MultiTrie
Contents
Description
A MultiTrie
v d
is a trie (i.e. a tree whose child nodes have distinct
labels, or atomic names, of type v
) with each node containing a list of values
of type d
that could be considered as a set or a multiset. It represents a
multivalued naming with compound names: each path, or a compound name (i.e. a
chain of labels) has a (possibly empty) list of values.
The simplest possible MultiTrie
is empty
that has an empty list of values
and no child nodes. Since the only essential feature of a MultiTrie
is
carrying values, the empty
MultiTrie
could be equated with an absense of a
MultiTrie
. In particular, instead of saying that there is no sub-trie under
some path in a MultiTrie
, let us say that the path points to an empty
node.
Therefore, every MultiTrie
could be considered as infinite, having child nodes
under all possible names - and some of the nodes are empty
.
Some operations could be defined for MultiTrie
s in a natural way, including
filter
, union
, intersection
, cartesian
. Obviously, empty
is a neutral
element of union
. Cartesian product is empty
if any of the two operands is
empty
.
A unary function f
can be applied to each value in each node of a MultiTrie
that results in a map
function. Moreover, a MultiTrie
can contain not only
ordinary values but also functions that makes it possible to apply a MultiTrie
of functions to a MultiTrie
of argument values, combining results with
cartesian
. A MultiTrie
whose values are, in their turn, MultiTrie
s, can
be flatten
ed. This makes MultiTrie
s an instance of Functor
, Applicative'
and Monad
classes.
For a detailed description of the multivalued naming with compound names as a a mathematical notion, its operations and properties, see an article distributed with this package as a LaTeX source.
- data MultiTrie v d
- empty :: MultiTrie v d
- singleton :: d -> MultiTrie v d
- leaf :: [d] -> MultiTrie v d
- repeat :: Ord v => [v] -> [d] -> MultiTrie v d
- updateValues :: ([d] -> [d]) -> MultiTrie v d -> MultiTrie v d
- addValue :: d -> MultiTrie v d -> MultiTrie v d
- values :: MultiTrie v d -> [d]
- children :: MultiTrie v d -> MultiTrieMap v d
- null :: MultiTrie v d -> Bool
- size :: MultiTrie v d -> Int
- areEqualStrict :: (Ord v, Eq d) => MultiTrie v d -> MultiTrie v d -> Bool
- areEqualWeak :: (Ord v, Eq d) => MultiTrie v d -> MultiTrie v d -> Bool
- areEquivalentUpTo :: (Ord v, Eq d) => ([d] -> [d] -> Bool) -> MultiTrie v d -> MultiTrie v d -> Bool
- subnode :: Ord v => [v] -> MultiTrie v d -> MultiTrie v d
- subnodeUpdate :: Ord v => [v] -> (MultiTrie v d -> MultiTrie v d) -> MultiTrie v d -> MultiTrie v d
- subnodeAddValue :: Ord v => [v] -> d -> MultiTrie v d -> MultiTrie v d
- subnodeReplace :: Ord v => [v] -> MultiTrie v d -> MultiTrie v d -> MultiTrie v d
- subnodeDelete :: Ord v => [v] -> MultiTrie v d -> MultiTrie v d
- subnodeUnite :: Ord v => [v] -> MultiTrie v d -> MultiTrie v d -> MultiTrie v d
- subnodeIntersect :: (Ord v, Eq d) => [v] -> MultiTrie v d -> MultiTrie v d -> MultiTrie v d
- filter :: Ord v => (d -> Bool) -> MultiTrie v d -> MultiTrie v d
- project :: Ord v => [[v]] -> MultiTrie v d -> MultiTrie v d
- filterOnNames :: Ord v => ([v] -> Bool) -> MultiTrie v d -> MultiTrie v d
- filterWithNames :: Ord v => ([v] -> d -> Bool) -> MultiTrie v d -> MultiTrie v d
- map :: Ord v => (d1 -> d2) -> MultiTrie v d1 -> MultiTrie v d2
- mapWithName :: Ord v => ([v] -> d1 -> d2) -> MultiTrie v d1 -> MultiTrie v d2
- mapMany :: Ord v => [d1 -> d2] -> MultiTrie v d1 -> MultiTrie v d2
- mapManyWithName :: Ord v => [[v] -> d1 -> d2] -> MultiTrie v d1 -> MultiTrie v d2
- mapOnLists :: Ord v => ([d1] -> [d2]) -> MultiTrie v d1 -> MultiTrie v d2
- mapOnListsWithName :: Ord v => ([v] -> [d1] -> [d2]) -> MultiTrie v d1 -> MultiTrie v d2
- cartesian :: Ord v => MultiTrie v d1 -> MultiTrie v d2 -> MultiTrie v (d1, d2)
- union :: Ord v => MultiTrie v d -> MultiTrie v d -> MultiTrie v d
- unions :: Ord v => [MultiTrie v d] -> MultiTrie v d
- intersection :: (Ord v, Eq d) => MultiTrie v d -> MultiTrie v d -> MultiTrie v d
- intersections1 :: (Ord v, Eq d) => [MultiTrie v d] -> MultiTrie v d
- flatten :: Ord v => MultiTrie v (MultiTrie v d) -> MultiTrie v d
- apply :: Ord v => MultiTrie v (d1 -> d2) -> MultiTrie v d1 -> MultiTrie v d2
- bind :: Ord v => MultiTrie v d1 -> (d1 -> MultiTrie v d2) -> MultiTrie v d2
- toMap :: Ord v => MultiTrie v d -> Map [v] [d]
- toList :: Ord v => MultiTrie v d -> [([v], d)]
- fromList :: Ord v => [([v], d)] -> MultiTrie v d
- fromMaybe :: Maybe (MultiTrie v d) -> MultiTrie v d
- toMaybe :: MultiTrie v d -> Maybe (MultiTrie v d)
- draw :: (Show v, Show [d]) => MultiTrie v d -> String
- listAsMultiSetEquals :: Eq a => [a] -> [a] -> Bool
- areMapsEquivalentUpTo :: Ord k => (a -> b -> Bool) -> Map k a -> Map k b -> Bool
Type
A trie consists of a list of values and labelled child tries.
Simple constructors
singleton :: d -> MultiTrie v d Source #
A MultiTrie
containing just one value in its root and no child nodes.
leaf :: [d] -> MultiTrie v d Source #
A MultiTrie
containing the given list in its root and no child nodes.
repeat :: Ord v => [v] -> [d] -> MultiTrie v d Source #
An infinite MultiTrie
that has in each node the same list of values and,
under each name from the given set, a child identical to the root.
updateValues :: ([d] -> [d]) -> MultiTrie v d -> MultiTrie v d Source #
Change a list in the root node with a function and leave children intact.
addValue :: d -> MultiTrie v d -> MultiTrie v d Source #
Add a new value to the root node's list of values.
Simple selectors
Comparison
areEqualStrict :: (Ord v, Eq d) => MultiTrie v d -> MultiTrie v d -> Bool Source #
Check for equality counting the order of elements.
areEqualWeak :: (Ord v, Eq d) => MultiTrie v d -> MultiTrie v d -> Bool Source #
Check for equality ignoring the order of elements.
areEquivalentUpTo :: (Ord v, Eq d) => ([d] -> [d] -> Bool) -> MultiTrie v d -> MultiTrie v d -> Bool Source #
Subnode access
subnodeUpdate :: Ord v => [v] -> (MultiTrie v d -> MultiTrie v d) -> MultiTrie v d -> MultiTrie v d Source #
Perform the given transformation on a subnode identified by the path.
subnodeAddValue :: Ord v => [v] -> d -> MultiTrie v d -> MultiTrie v d Source #
Add a value to a list of values in a subnode identified by the path.
subnodeReplace :: Ord v => [v] -> MultiTrie v d -> MultiTrie v d -> MultiTrie v d Source #
Replace a subnode identified by the path with a new MultiTrie
.
subnodeDelete :: Ord v => [v] -> MultiTrie v d -> MultiTrie v d Source #
Delete a subnode identified by the given path.
subnodeUnite :: Ord v => [v] -> MultiTrie v d -> MultiTrie v d -> MultiTrie v d Source #
Unite a subnode identified by the path with another MultiTrie
.
subnodeIntersect :: (Ord v, Eq d) => [v] -> MultiTrie v d -> MultiTrie v d -> MultiTrie v d Source #
Intersect a subnode identified by the path with another MultiTrie
.
Filtration
filter :: Ord v => (d -> Bool) -> MultiTrie v d -> MultiTrie v d Source #
Leave only those values that satisfy the predicate p
.
project :: Ord v => [[v]] -> MultiTrie v d -> MultiTrie v d Source #
Leave only the nodes whose compound names are in the given list.
filterOnNames :: Ord v => ([v] -> Bool) -> MultiTrie v d -> MultiTrie v d Source #
Leave only those nodes whose compound names satisfy the predicate p
.
filterWithNames :: Ord v => ([v] -> d -> Bool) -> MultiTrie v d -> MultiTrie v d Source #
Leave only those values that, with their compound names, satisfy the
predicate p
.
Mappings
map :: Ord v => (d1 -> d2) -> MultiTrie v d1 -> MultiTrie v d2 Source #
Map a function over all values in a MultiTrie
.
mapWithName :: Ord v => ([v] -> d1 -> d2) -> MultiTrie v d1 -> MultiTrie v d2 Source #
Map a function over all values with their compound names.
mapMany :: Ord v => [d1 -> d2] -> MultiTrie v d1 -> MultiTrie v d2 Source #
Apply a list of functions to all values in a MultiTrie
.
mapManyWithName :: Ord v => [[v] -> d1 -> d2] -> MultiTrie v d1 -> MultiTrie v d2 Source #
Apply a list of functions to each value and its compound name.
mapOnLists :: Ord v => ([d1] -> [d2]) -> MultiTrie v d1 -> MultiTrie v d2 Source #
Map a function over entire lists contained in nodes.
mapOnListsWithName :: Ord v => ([v] -> [d1] -> [d2]) -> MultiTrie v d1 -> MultiTrie v d2 Source #
Map a function over entire lists in all nodes, with their compound names.
High-level operations
intersection :: (Ord v, Eq d) => MultiTrie v d -> MultiTrie v d -> MultiTrie v d Source #
Intersection of MultiTrie
s.
intersections1 :: (Ord v, Eq d) => [MultiTrie v d] -> MultiTrie v d Source #
Intersection of a non-empty list of MultiTrie
s.
Applications
Conversions
toList :: Ord v => MultiTrie v d -> [([v], d)] Source #
Convert a MultiTrie
to a list of path-value pairs.
fromList :: Ord v => [([v], d)] -> MultiTrie v d Source #
Convert a list of path-value pairs to a MultiTrie
.
toMaybe :: MultiTrie v d -> Maybe (MultiTrie v d) Source #
Map empty
to Nothing
and a non-empty t
to Just t
.
Debug
draw :: (Show v, Show [d]) => MultiTrie v d -> String Source #
Convert a MultiTrie
into an ASCII-drawn tree.
Other
listAsMultiSetEquals :: Eq a => [a] -> [a] -> Bool Source #
Check if two lists are equal as multisets, i.e. if they have equal numbers of equal values.
areMapsEquivalentUpTo :: Ord k => (a -> b -> Bool) -> Map k a -> Map k b -> Bool Source #
Decide if maps are equivalent up to a custom value equivalence predicate.
True if and only if the maps have exactly the same names and, for each name,
its values in the two maps are equivalent. Map
is missing this.