-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Trie of sets, as a model for compound names having multiple values -- -- A multi-trie is a trie (i.e. a tree whose child nodes have distinct -- labels) with each node containing a list of values. This data -- structure represents a structured many-valued naming: names are -- compound and form a monoid under concatenation; each name can have -- multiple values. Some operations could be defined for multi-tries in a -- rather natural way, including map, union, -- intersection, cartesian product. Moreover, a multi-trie -- can contain not only ordinary values but also functions that makes it -- possible to apply a multi-trie of functions to a multi-trie of -- argument values. This makes MultiTrie an instance of -- Functor, Applicative and Monad. @package multi-trie @version 0.1 -- | 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 MultiTries 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, MultiTries, can be flattened. This makes -- MultiTries 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. module Data.MultiTrie -- | A trie consists of a list of values and labelled child tries. data MultiTrie v d -- | An empty MultiTrie constant. A neutral element of union -- and zero of cartesian. empty :: MultiTrie v d -- | A MultiTrie containing just one value in its root and no child -- nodes. singleton :: d -> MultiTrie v d -- | A MultiTrie containing the given list in its root and no child -- nodes. leaf :: [d] -> MultiTrie v d -- | 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. repeat :: Ord v => [v] -> [d] -> MultiTrie v d -- | Change a list in the root node with a function and leave children -- intact. updateValues :: ([d] -> [d]) -> MultiTrie v d -> MultiTrie v d -- | Add a new value to the root node's list of values. addValue :: d -> MultiTrie v d -> MultiTrie v d -- | List of values in the root node. values :: MultiTrie v d -> [d] -- | Map of atomic names to child sub-tries. children :: MultiTrie v d -> MultiTrieMap v d -- | Check if a MultiTrie is empty. null :: MultiTrie v d -> Bool -- | A total number of values in all nodes. size :: MultiTrie v d -> Int -- | Check for equality counting the order of elements. areEqualStrict :: (Ord v, Eq d) => MultiTrie v d -> MultiTrie v d -> Bool -- | Check for equality ignoring the order of elements. areEqualWeak :: (Ord v, Eq d) => MultiTrie v d -> MultiTrie v d -> Bool -- | Check if two MultiTries, t1 and t2, are -- equivalent up to a custom list equivalence predicate p. True -- if and only if (1) both MultiTries have non-empty nodes at the -- same paths and (2) for each such path w, value lists from -- t1 and t2 under w are equivalent, i.e. -- satisfy p. areEquivalentUpTo :: (Ord v, Eq d) => ([d] -> [d] -> Bool) -> MultiTrie v d -> MultiTrie v d -> Bool -- | Select a MultiTrie subnode identified by the given path, or -- empty if there is no such path. subnode :: Ord v => [v] -> MultiTrie v d -> MultiTrie v d -- | Perform the given transformation on a subnode identified by the path. subnodeUpdate :: Ord v => [v] -> (MultiTrie v d -> MultiTrie v d) -> MultiTrie v d -> MultiTrie v d -- | Add a value to a list of values in a subnode identified by the path. subnodeAddValue :: Ord v => [v] -> d -> MultiTrie v d -> MultiTrie v d -- | Replace a subnode identified by the path with a new MultiTrie. subnodeReplace :: Ord v => [v] -> MultiTrie v d -> MultiTrie v d -> MultiTrie v d -- | Delete a subnode identified by the given path. subnodeDelete :: Ord v => [v] -> MultiTrie v d -> MultiTrie v d -- | Unite a subnode identified by the path with another MultiTrie. subnodeUnite :: Ord v => [v] -> MultiTrie v d -> MultiTrie v d -> MultiTrie v d -- | Intersect a subnode identified by the path with another -- MultiTrie. subnodeIntersect :: (Ord v, Eq d) => [v] -> MultiTrie v d -> MultiTrie v d -> MultiTrie v d -- | Leave only those values that satisfy the predicate p. filter :: Ord v => (d -> Bool) -> MultiTrie v d -> MultiTrie v d -- | Leave only the nodes whose compound names are in the given list. project :: Ord v => [[v]] -> MultiTrie v d -> MultiTrie v d -- | Leave only those nodes whose compound names satisfy the predicate -- p. filterOnNames :: Ord v => ([v] -> Bool) -> MultiTrie v d -> MultiTrie v d -- | Leave only those values that, with their compound names, satisfy the -- predicate p. filterWithNames :: Ord v => ([v] -> d -> Bool) -> MultiTrie v d -> MultiTrie v d -- | Map a function over all values in a MultiTrie. map :: Ord v => (d1 -> d2) -> MultiTrie v d1 -> MultiTrie v d2 -- | Map a function over all values with their compound names. mapWithName :: Ord v => ([v] -> d1 -> d2) -> MultiTrie v d1 -> MultiTrie v d2 -- | Apply a list of functions to all values in a MultiTrie. mapMany :: Ord v => [d1 -> d2] -> MultiTrie v d1 -> MultiTrie v d2 -- | Apply a list of functions to each value and its compound name. mapManyWithName :: Ord v => [[v] -> d1 -> d2] -> MultiTrie v d1 -> MultiTrie v d2 -- | Map a function over entire lists contained in nodes. mapOnLists :: Ord v => ([d1] -> [d2]) -> MultiTrie v d1 -> MultiTrie v d2 -- | Map a function over entire lists in all nodes, with their compound -- names. mapOnListsWithName :: Ord v => ([v] -> [d1] -> [d2]) -> MultiTrie v d1 -> MultiTrie v d2 -- | Cartesian product of two MultiTries, t1 and -- t2. The resulting MultiTrie consists of all possible -- pairs (x1, x2) under a concatenated name v1 ++ v2 -- where x1 is a value in t1 under a name v1, -- and x2 is a value from t2 under the name -- v2. cartesian :: Ord v => MultiTrie v d1 -> MultiTrie v d2 -> MultiTrie v (d1, d2) -- | Union of MultiTries. union :: Ord v => MultiTrie v d -> MultiTrie v d -> MultiTrie v d -- | Union of a list of MultiTries. unions :: Ord v => [MultiTrie v d] -> MultiTrie v d -- | Intersection of MultiTries. intersection :: (Ord v, Eq d) => MultiTrie v d -> MultiTrie v d -> MultiTrie v d -- | Intersection of a non-empty list of MultiTries. intersections1 :: (Ord v, Eq d) => [MultiTrie v d] -> MultiTrie v d -- | Flatten a MultiTrie whose values are, in their turn, -- MultiTries. flatten :: Ord v => MultiTrie v (MultiTrie v d) -> MultiTrie v d -- | Given a MultiTrie t1 of functions and a -- MultiTrie t2 of values, for all compound names -- v1 and v2, apply each function named by v1 -- in t1 to each value named by v2 in t2 and -- put the result into a new MultiTrie under a name v1 ++ -- v2. apply :: Ord v => MultiTrie v (d1 -> d2) -> MultiTrie v d1 -> MultiTrie v d2 -- | Given a MultiTrie t of values and a function -- f that maps an arbitrary value to a MultiTrie, apply -- the function f to each value from t and -- flatten the result. bind :: Ord v => MultiTrie v d1 -> (d1 -> MultiTrie v d2) -> MultiTrie v d2 -- | Convert a MultiTrie t to a Map of compound -- names into value lists. toMap :: Ord v => MultiTrie v d -> Map [v] [d] -- | Convert a MultiTrie to a list of path-value pairs. toList :: Ord v => MultiTrie v d -> [([v], d)] -- | Convert a list of path-value pairs to a MultiTrie. fromList :: Ord v => [([v], d)] -> MultiTrie v d -- | Map Nothing to empty and Just t to -- t. fromMaybe :: Maybe (MultiTrie v d) -> MultiTrie v d -- | Map empty to Nothing and a non-empty t to -- Just t. toMaybe :: MultiTrie v d -> Maybe (MultiTrie v d) -- | Convert a MultiTrie into an ASCII-drawn tree. draw :: (Show v, Show [d]) => MultiTrie v d -> String -- | Check if two lists are equal as multisets, i.e. if they have equal -- numbers of equal values. listAsMultiSetEquals :: Eq a => [a] -> [a] -> Bool -- | 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. areMapsEquivalentUpTo :: Ord k => (a -> b -> Bool) -> Map k a -> Map k b -> Bool instance (GHC.Show.Show v, GHC.Show.Show d) => GHC.Show.Show (Data.MultiTrie.MultiTrie v d) instance GHC.Classes.Ord v => GHC.Base.Functor (Data.MultiTrie.MultiTrie v) instance GHC.Classes.Ord v => GHC.Base.Applicative (Data.MultiTrie.MultiTrie v) instance GHC.Classes.Ord v => GHC.Base.Monad (Data.MultiTrie.MultiTrie v) instance (GHC.Classes.Ord v, GHC.Classes.Eq d) => GHC.Classes.Eq (Data.MultiTrie.MultiTrie v d)