Portability | portable |
---|---|
Stability | provisional |
Maintainer | http://homepages.nildram.co.uk/~ahey/em.png |
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.
- data Set a
- (\\) :: Ord a => Set a -> Set a -> Set a
- null :: Set a -> Bool
- size :: Set a -> Int
- member :: Ord a => a -> Set a -> Bool
- isSubsetOf :: Ord a => Set a -> Set a -> Bool
- isProperSubsetOf :: Ord a => Set a -> Set a -> Bool
- empty :: Set a
- singleton :: a -> Set a
- insert :: Ord a => a -> Set a -> Set a
- delete :: Ord a => a -> Set a -> Set a
- union :: Ord a => Set a -> Set a -> Set a
- unions :: Ord a => [Set a] -> Set a
- difference :: Ord a => Set a -> Set a -> Set a
- intersection :: Ord a => Set a -> Set a -> Set a
- filter :: Ord a => (a -> Bool) -> Set a -> Set a
- partition :: Ord a => (a -> Bool) -> Set a -> (Set a, Set a)
- split :: Ord a => a -> Set a -> (Set a, Set a)
- splitMember :: Ord a => a -> Set a -> (Set a, Bool, Set a)
- map :: (Ord a, Ord b) => (a -> b) -> Set a -> Set b
- mapMonotonic :: (a -> b) -> Set a -> Set b
- fold :: (a -> b -> b) -> b -> Set a -> b
- findMin :: Set a -> a
- findMax :: Set a -> a
- deleteMin :: Set a -> Set a
- deleteMax :: Set a -> Set a
- deleteFindMin :: Set a -> (a, Set a)
- deleteFindMax :: Set a -> (a, Set a)
- elems :: Set a -> [a]
- toList :: Set a -> [a]
- fromList :: Ord a => [a] -> Set a
- toAscList :: Set a -> [a]
- fromAscList :: Eq a => [a] -> Set a
- fromDistinctAscList :: [a] -> Set a
- toStdSet :: Set a -> Set a
- fromStdSet :: Set a -> Set a
- toTree :: Set a -> AVL a
- unsafeFromTree :: AVL a -> Set a
- valid :: Ord a => Set a -> Bool
- emptySet :: Set a
- mkSet :: Ord a => [a] -> Set a
- setToList :: Set a -> [a]
- unitSet :: a -> Set a
- elementOf :: Ord a => a -> Set a -> Bool
- isEmptySet :: Set a -> Bool
- cardinality :: Set a -> Int
- unionManySets :: Ord a => [Set a] -> Set a
- minusSet :: Ord a => Set a -> Set a -> Set a
- mapSet :: (Ord a, Ord b) => (b -> a) -> Set b -> Set a
- intersect :: Ord a => Set a -> Set a -> Set a
- addToSet :: Ord a => Set a -> a -> Set a
- delFromSet :: Ord a => Set a -> a -> Set a
Set type
A set of values a
.
Operators
Query
isSubsetOf :: Ord a => Set a -> Set a -> BoolSource
O(?). Is this a subset?
(s1
tells whether isSubsetOf
s2)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
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.
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.
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 (
) is a pair split
x set(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).
is the set obtained by applying map
f sf
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
, works only when mapMonotonic
f s == map
f sf
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
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
Ordered list
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
Old interface, DEPRECATED
isEmptySet :: Set a -> BoolSource
Obsolete equivalent of null
.
cardinality :: Set a -> IntSource
Obsolete equivalent of size
.