collections-0.3.1: Useful standard collections types and related functions.

Portability portable provisional http://homepages.nildram.co.uk/~ahey/em.png

Data.Set.AVL

Description

This module provides an AVL tree based clone of the base package Data.Set.

There are some differences though..

• `size` is O(n), not O(1)
• The showTree and showTreeWith functions are not implemented.
• The complexities of `isSubsetOf`,`isProperSubsetOf`,`union`,`intersection`,`difference` are unknown (because my maths isn't good enough to figure it out), but are probably no worse than the originals.
• Conversion functions `toTree`, `unsafeFromTree`, `toStdSet`, `fromStdSet`. have been added.

Synopsis

# Set type

data Set a Source

A set of values `a`.

Instances

 Typeable1 Set Eq a => Eq (Set a) (Data a, Ord a) => Data (Set a) Ord a => Ord (Set a) Show a => Show (Set a) Ord a => Monoid (Set a) Foldable (Set a) a Ord a => Set (Set a) a Ord a => SortingCollection (Set a) a Ord a => Unfoldable (Set a) a Ord a => Collection (Set a) a Ord a => Map (Set a) a ()

# Operators

(\\) :: Ord a => Set a -> Set a -> Set aSource

O(?). See `difference`.

# Query

null :: Set a -> BoolSource

O(1). Is this the empty set?

size :: Set a -> IntSource

O(n). The number of elements in the set.

member :: Ord a => a -> Set a -> BoolSource

O(log n). Is the element in the set?

isSubsetOf :: Ord a => Set a -> Set a -> BoolSource

O(?). Is this a subset? `(s1 isSubsetOf s2)` tells whether `s1` is a subset of `s2`.

isProperSubsetOf :: Ord a => Set a -> Set a -> BoolSource

O(?). Is this a proper subset? (ie. a subset but not equal).

# Construction

O(1). The empty set.

singleton :: a -> Set aSource

O(1). Create a singleton set.

insert :: Ord a => a -> Set a -> Set aSource

O(log n). Insert an element in a set. If the set already contains an element equal to the given value, it is replaced with the new value.

delete :: Ord a => a -> Set a -> Set aSource

O(log n). Delete an element from a set.

# Combine

union :: Ord a => Set a -> Set a -> Set aSource

O(?). The union of two sets, preferring the first set when equal elements are encountered.

unions :: Ord a => [Set a] -> Set aSource

The union of a list of sets: (`unions == foldl' union empty`).

difference :: Ord a => Set a -> Set a -> Set aSource

O(?). Difference of two sets.

intersection :: Ord a => Set a -> Set a -> Set aSource

O(?). The intersection of two sets.

# Filter

filter :: Ord a => (a -> Bool) -> Set a -> Set aSource

O(n). Filter all elements that satisfy the predicate.

partition :: Ord a => (a -> Bool) -> Set a -> (Set a, Set a)Source

O(n). Partition the set into two sets, one with all elements that satisfy the predicate and one with all elements that don't satisfy the predicate. See also `split`.

split :: Ord a => a -> Set a -> (Set a, Set a)Source

O(log n). The expression (`split x set`) is a pair `(set1,set2)` where all elements in `set1` are lower than `x` and all elements in `set2` larger than `x`. `x` is not found in neither `set1` nor `set2`.

splitMember :: Ord a => a -> Set a -> (Set a, Bool, Set a)Source

O(log n). Performs a `split` but also returns whether the pivot element was found in the original set.

# Map

map :: (Ord a, Ord b) => (a -> b) -> Set a -> Set bSource

O(n*log n). `map f s` is the set obtained by applying `f` to each element of `s`.

It's worth noting that the size of the result may be smaller if, for some `(x,y)`, `x /= y && f x == f y`

mapMonotonic :: (a -> b) -> Set a -> Set bSource

O(n). The identity

`mapMonotonic f s == map f s`, works only when `f` is monotonic. The precondition is not checked. Semi-formally, we have:

``` and [x < y ==> f x < f y | x <- ls, y <- ls]
==> mapMonotonic f s == map f s
where ls = toList s
```

# Fold

fold :: (a -> b -> b) -> b -> Set a -> bSource

O(n). Fold over the elements of a set in an unspecified order.

# Min/Max

findMin :: Set a -> aSource

O(log n). The minimal element of a set.

findMax :: Set a -> aSource

O(log n). The maximal element of a set.

deleteMin :: Set a -> Set aSource

O(log n). Delete the minimal element.

deleteMax :: Set a -> Set aSource

O(log n). Delete the maximal element.

deleteFindMin :: Set a -> (a, Set a)Source

O(log n). Delete and find the minimal element.

``` deleteFindMin set = (findMin set, deleteMin set)
```

deleteFindMax :: Set a -> (a, Set a)Source

O(log n). Delete and find the maximal element.

``` deleteFindMax set = (findMax set, deleteMax set)
```

# Conversion

## List

elems :: Set a -> [a]Source

O(n). The elements of a set.

toList :: Set a -> [a]Source

O(n). Convert the set to a list of elements.

fromList :: Ord a => [a] -> Set aSource

O(n*log n). Create a set from a list of elements.

## Ordered list

toAscList :: Set a -> [a]Source

O(n). Convert the set to an ascending list of elements.

fromAscList :: Eq a => [a] -> Set aSource

O(n). Build a set from an ascending list in linear time. The precondition (input list is ascending) is not checked.

fromDistinctAscList :: [a] -> Set aSource

O(n). Build a set from an ascending list of distinct elements in linear time. The precondition (input list is strictly ascending) is not checked.

## To/From Data.Set.Set

toStdSet :: Set a -> Set aSource

O(n). Convert an AVL tree based Set (as provided by this module) to a Data.Set.Set.

fromStdSet :: Set a -> Set aSource

O(n). Convert a Data.Set.Set to an AVL tree based Set (as provided by this module).

## To/From raw AVL trees.

These conversions allow you to use the functions provided by Data.Tree.AVL.

toTree :: Set a -> AVL aSource

O(1). Convert an AVL tree based Set (as provided by this module) to a sorted AVL tree.

unsafeFromTree :: AVL a -> Set aSource

O(1). Convert a sorted AVL tree to an AVL tree based Set (as provided by this module). This function does not check the input AVL tree is sorted.

# Debugging

valid :: Ord a => Set a -> BoolSource

O(n). Test if the internal set structure is valid.

# Old interface, DEPRECATED

Obsolete equivalent of `empty`.

mkSet :: Ord a => [a] -> Set aSource

Obsolete equivalent of `fromList`.

setToList :: Set a -> [a]Source

Obsolete equivalent of `elems`.

unitSet :: a -> Set aSource

Obsolete equivalent of `singleton`.

elementOf :: Ord a => a -> Set a -> BoolSource

Obsolete equivalent of `member`.

isEmptySet :: Set a -> BoolSource

Obsolete equivalent of `null`.

cardinality :: Set a -> IntSource

Obsolete equivalent of `size`.

unionManySets :: Ord a => [Set a] -> Set aSource

Obsolete equivalent of `unions`.

minusSet :: Ord a => Set a -> Set a -> Set aSource

Obsolete equivalent of `difference`.

mapSet :: (Ord a, Ord b) => (b -> a) -> Set b -> Set aSource

Obsolete equivalent of `map`.

intersect :: Ord a => Set a -> Set a -> Set aSource

Obsolete equivalent of `intersection`.

addToSet :: Ord a => Set a -> a -> Set aSource

Obsolete equivalent of `flip insert`.

delFromSet :: Ord a => Set a -> a -> Set aSource

Obsolete equivalent of `flip delete`.