Haskell Hierarchical Libraries (collections package)ContentsIndex
Data.Tree.AVL.Set
Portabilityportable
Stabilitystable
Maintainerhttp://homepages.nildram.co.uk/~ahey/em.png
Contents
General purpose set operations.
Union.
Difference.
Intersection.
Intersection with the result as a list.
Subset.
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
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 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 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 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' (genUnion ccmp) empty avls
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 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 a

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 e

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

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]

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]

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]

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