| |||||||||||||||||||||||||

| |||||||||||||||||||||||||

| |||||||||||||||||||||||||

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).
| |||||||||||||||||||||||||

Synopsis | |||||||||||||||||||||||||

| |||||||||||||||||||||||||

General purpose set operations. | |||||||||||||||||||||||||

Union. | |||||||||||||||||||||||||

genUnion :: (e -> e -> COrdering e) -> AVL e -> AVL e -> AVL e | |||||||||||||||||||||||||

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 e | |||||||||||||||||||||||||

Similar to Complexity: Not sure, but I'd appreciate it if someone could figure it out. | |||||||||||||||||||||||||

genUnions :: (e -> e -> COrdering e) -> [AVL e] -> AVL e | |||||||||||||||||||||||||

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' ( | |||||||||||||||||||||||||

Difference. | |||||||||||||||||||||||||

genDifference :: (a -> b -> Ordering) -> AVL a -> AVL b -> AVL a | |||||||||||||||||||||||||

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 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 a | |||||||||||||||||||||||||

Similar to Complexity: Not sure, but I'd appreciate it if someone could figure it out. | |||||||||||||||||||||||||

genSymDifference :: (e -> e -> Ordering) -> AVL e -> AVL e -> AVL e | |||||||||||||||||||||||||

The symmetric difference is the set of elements which occur in one set or the other but 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 c | |||||||||||||||||||||||||

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 c | |||||||||||||||||||||||||

Similar to 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] | |||||||||||||||||||||||||

Similar to 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] | |||||||||||||||||||||||||

Applies 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] | |||||||||||||||||||||||||

Similar to 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] | |||||||||||||||||||||||||

Applies Complexity: Not sure, but I'd appreciate it if someone could figure it out. | |||||||||||||||||||||||||

Subset. | |||||||||||||||||||||||||

genIsSubsetOf :: (a -> b -> Ordering) -> AVL a -> AVL b -> Bool | |||||||||||||||||||||||||

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. | |||||||||||||||||||||||||

Produced by Haddock version 0.7 |