| Portability | portable |
|---|---|
| Stability | stable |
| Maintainer | http://homepages.nildram.co.uk/~ahey/em.png |
Data.Tree.AVL.Set
Contents
Description
Functions for manipulating AVL trees which represent ordered sets (I.E. sorted trees). Note that although many of these functions work with a variety of different element types they all require that elements are sorted according to the same criterion (such as a field value in a record).
- genUnion :: (e -> e -> COrdering e) -> AVL e -> AVL e -> AVL e
- genUnionMaybe :: (e -> e -> COrdering (Maybe e)) -> AVL e -> AVL e -> AVL e
- genUnions :: (e -> e -> COrdering e) -> [AVL e] -> AVL e
- genDifference :: (a -> b -> Ordering) -> AVL a -> AVL b -> AVL a
- genDifferenceMaybe :: (a -> b -> COrdering (Maybe a)) -> AVL a -> AVL b -> AVL a
- genSymDifference :: (e -> e -> Ordering) -> AVL e -> AVL e -> AVL e
- genIntersection :: (a -> b -> COrdering c) -> AVL a -> AVL b -> AVL c
- genIntersectionMaybe :: (a -> b -> COrdering (Maybe c)) -> AVL a -> AVL b -> AVL c
- genIntersectionToListL :: (a -> b -> COrdering c) -> AVL a -> AVL b -> [c] -> [c]
- genIntersectionAsListL :: (a -> b -> COrdering c) -> AVL a -> AVL b -> [c]
- genIntersectionMaybeToListL :: (a -> b -> COrdering (Maybe c)) -> AVL a -> AVL b -> [c] -> [c]
- genIntersectionMaybeAsListL :: (a -> b -> COrdering (Maybe c)) -> AVL a -> AVL b -> [c]
- genIsSubsetOf :: (a -> b -> Ordering) -> AVL a -> AVL b -> Bool
General purpose set operations.
Union.
genUnion :: (e -> e -> COrdering e) -> AVL e -> AVL e -> AVL eSource
Uses the supplied combining comparison to evaluate the union of two sets represented as sorted AVL trees. Whenever the combining comparison is applied, the first comparison argument is an element of the first tree and the second comparison argument is an element of the second tree.
Complexity: Not sure, but I'd appreciate it if someone could figure it out. (Faster than Hedge union from Data.Set at any rate).
genUnionMaybe :: (e -> e -> COrdering (Maybe e)) -> AVL e -> AVL e -> AVL eSource
Similar to genUnion, but the resulting tree does not include elements in cases where
the supplied combining comparison returns (Eq Nothing).
Complexity: Not sure, but I'd appreciate it if someone could figure it out.
genUnions :: (e -> e -> COrdering e) -> [AVL e] -> AVL eSource
Uses the supplied combining comparison to evaluate the union of all sets in a list of sets represented as sorted AVL trees. Behaves as if defined..
genUnions ccmp avls = foldl' (genUnion ccmp) empty avlsDifference.
genDifference :: (a -> b -> Ordering) -> AVL a -> AVL b -> AVL aSource
Uses the supplied comparison to evaluate the difference between two sets represented as sorted AVL trees. The expression..
genDifference cmp setA setB
.. is a set containing all those elements of setA which do not appear in setB.
Complexity: Not sure, but I'd appreciate it if someone could figure it out.
genDifferenceMaybe :: (a -> b -> COrdering (Maybe a)) -> AVL a -> AVL b -> AVL aSource
Similar to genDifference, but the resulting tree also includes those elements a' for which the
combining comparison returns (Eq (Just a')).
Complexity: Not sure, but I'd appreciate it if someone could figure it out.
genSymDifference :: (e -> e -> Ordering) -> AVL e -> AVL e -> AVL eSource
The symmetric difference is the set of elements which occur in one set or the other but not both.
Complexity: Not sure, but I'd appreciate it if someone could figure it out.
Intersection.
genIntersection :: (a -> b -> COrdering c) -> AVL a -> AVL b -> AVL cSource
Uses the supplied combining comparison to evaluate the intersection of two sets represented as sorted AVL trees.
Complexity: Not sure, but I'd appreciate it if someone could figure it out.
genIntersectionMaybe :: (a -> b -> COrdering (Maybe c)) -> AVL a -> AVL b -> AVL cSource
Similar to genIntersection, but the resulting tree does not include elements in cases where
the supplied combining comparison returns (Eq Nothing).
Complexity: Not sure, but I'd appreciate it if someone could figure it out.
Intersection with the result as a list.
Sometimes you don't want intersection to give a tree, particularly if the resulting elements are not orderered or sorted according to whatever criterion was used to sort the elements of the input sets.
BTW, the reason these variants are provided for intersection only (and not the other set functions) is that the (tree returning) intersections always construct an entirely new tree, whereas with the others the resulting tree will typically share sub-trees with one or both of the originals. (Of course the results of the others can easily be converted to a list too if required.)
genIntersectionToListL :: (a -> b -> COrdering c) -> AVL a -> AVL b -> [c] -> [c]Source
Similar to genIntersection, but prepends the result to the supplied list in
left to right order. This is a (++) free function which behaves as if defined:
genIntersectionToListL c setA setB cs = asListL (genIntersection c setA setB) ++ cs
Complexity: Not sure, but I'd appreciate it if someone could figure it out.
genIntersectionAsListL :: (a -> b -> COrdering c) -> AVL a -> AVL b -> [c]Source
Applies genIntersectionToListL to the empty list.
Complexity: Not sure, but I'd appreciate it if someone could figure it out.
genIntersectionMaybeToListL :: (a -> b -> COrdering (Maybe c)) -> AVL a -> AVL b -> [c] -> [c]Source
Similar to genIntersectionToListL, but the result does not include elements in cases where
the supplied combining comparison returns (Eq Nothing).
Complexity: Not sure, but I'd appreciate it if someone could figure it out.
genIntersectionMaybeAsListL :: (a -> b -> COrdering (Maybe c)) -> AVL a -> AVL b -> [c]Source
Applies genIntersectionMaybeToListL to the empty list.
Complexity: Not sure, but I'd appreciate it if someone could figure it out.
Subset.
genIsSubsetOf :: (a -> b -> Ordering) -> AVL a -> AVL b -> BoolSource
Uses the supplied comparison to test whether the first set is a subset of the second, both sets being represented as sorted AVL trees. This function returns True if any of the following conditions hold..
- The first set is empty (the empty set is a subset of any set).
- The two sets are equal.
- The first set is a proper subset of the second set.
Complexity: Not sure, but I'd appreciate it if someone could figure it out.