Portability | portable |
---|---|

Stability | stable |

Maintainer | http://homepages.nildram.co.uk/~ahey/em.png |

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 avls

## Difference.

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.