hets -- a heterogenous Specification (CASL) tool setContentsIndex
Common.Lib.Set
Portability portable
Stability provisional
Maintainer daan@cs.uu.nl
Contents
Set type
Operators
Query
Construction
Combine
Filter
Fold
Min/Max
Conversion
List
Maybe
Ordered list
Debugging
Description

An efficient implementation of sets.

1) The filter function clashes with the Prelude. If you want to use Set unqualified, this function should be hidden.

 import Prelude hiding (filter)
 import Set

Another solution is to use qualified names. This is also the only way how a Map, Set, and MultiSet can be used within one module.

 import qualified Set

 ... Set.single "Paris" 

Or, if you prefer a terse coding style:

 import qualified Set as S

 ... S.single "Berlin" 

2) The implementation of Set is based on size balanced binary trees (or trees of bounded balance) as described by:

  • Stephen Adams, "Efficient sets: a balancing act", Journal of Functional Programming 3(4):553-562, October 1993, http://www.swiss.ai.mit.edu/~adams/BB.
  • J. Nievergelt and E.M. Reingold, "Binary search trees of bounded balance", SIAM journal of computing 2(1), March 1973.

3) Note that the implementation left-biased -- the elements of a first argument are always perferred to the second, for example in union or insert. Off course, left-biasing can only be observed when equality an equivalence relation instead of structural equality.

4) Another implementation of sets based on size balanced trees exists as Data.Set in the Ghc libraries. The good part about this library is that it is highly tuned and thorougly tested. However, it is also fairly old, it is implemented indirectly on top of Data.FiniteMap and only supports the basic set operations. The Set module overcomes some of these issues:

  • It tries to export a more complete and consistent set of operations, like partition, subset etc.
  • It uses the efficient hedge algorithm for both union and difference (a hedge algorithm is not applicable to intersection).
  • It converts ordered lists in linear time (fromAscList).
  • It takes advantage of the module system with names like empty instead of emptySet.
  • It is implemented directly, instead of using a seperate finite map implementation.
Synopsis
data Set a
(\\) :: Ord a => Set a -> Set a -> Set a
isEmpty :: Set a -> Bool
size :: Set a -> Int
member :: Ord a => a -> Set a -> Bool
subset :: Ord a => Set a -> Set a -> Bool
properSubset :: Ord a => Set a -> Set a -> Bool
empty :: Set a
single :: 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
disjoint :: Ord a => Set a -> Set a -> Bool
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 -> (Bool, Set a, Set a)
all :: Ord a => (a -> Bool) -> Set a -> Bool
any :: Ord a => (a -> Bool) -> Set a -> Bool
fold :: (a -> b -> b) -> b -> Set a -> b
image :: Ord b => (a -> b) -> Set a -> Set 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
maybeToSet :: Maybe a -> Set a
maybeSetToSet :: Maybe (Set a) -> Set a
toAscList :: Set a -> [a]
fromAscList :: Eq a => [a] -> Set a
fromDistinctAscList :: [a] -> Set a
showTree :: Show a => Set a -> String
showTreeWith :: Show a => Bool -> Bool -> Set a -> String
valid :: Ord a => Set a -> Bool
Set type
data Set a
A set of values a.
Instances
(Ord a, ATermConvertible a) => ATermConvertible (Set a)
Eq a => Eq (Set a)
Ord a => Ord (Set a)
Show a => Show (Set a)
PrettyPrint a => PrettyPrint (Set a)
Typeable a => Typeable (Set a)
Operators
(\\) :: Ord a => Set a -> Set a -> Set a
O(n+m). See difference.
Query
isEmpty :: Set a -> Bool
O(1). Is this the empty set?
size :: Set a -> Int
O(1). The number of elements in the set.
member :: Ord a => a -> Set a -> Bool
O(log n). Is the element in the set?
subset :: Ord a => Set a -> Set a -> Bool
O(n+m). Is this a subset?
properSubset :: Ord a => Set a -> Set a -> Bool
O(n+m). Is this a proper subset? (ie. a subset but not equal).
Construction
empty :: Set a
O(1). The empty set.
single :: a -> Set a
O(1). Create a singleton set.
insert :: Ord a => a -> Set a -> Set a
O(log n). Insert an element in a set.
delete :: Ord a => a -> Set a -> Set a
O(log n). Delete an element from a set.
Combine
union :: Ord a => Set a -> Set a -> Set a
O(n+m). The union of two sets. Uses the efficient hedge-union algorithm.
unions :: Ord a => [Set a] -> Set a
The union of a list of sets: (unions == foldl union empty).
difference :: Ord a => Set a -> Set a -> Set a
O(n+m). Difference of two sets. The implementation uses an efficient hedge algorithm comparable with hedge-union.
intersection :: Ord a => Set a -> Set a -> Set a
O(n+m). The intersection of two sets.
disjoint :: Ord a => Set a -> Set a -> Bool
O(n+m). Are two sets disjoint?
Filter
filter :: Ord a => (a -> Bool) -> Set a -> Set a
O(n). Filter all elements that satisfy the predicate.
partition :: Ord a => (a -> Bool) -> Set a -> (Set a, Set a)
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)
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.
splitMember :: Ord a => a -> Set a -> (Bool, Set a, Set a)
O(log n). Performs a split but also returns whether the pivot element was found in the original set.
all :: Ord a => (a -> Bool) -> Set a -> Bool
O(n). Do all elements satisfy the predicate?
any :: Ord a => (a -> Bool) -> Set a -> Bool
O(n). Does some element satisfy the predicate?
Fold
fold :: (a -> b -> b) -> b -> Set a -> b
O(n). Fold the elements of a set.
image :: Ord b => (a -> b) -> Set a -> Set b
n. Image of a set under a function
Min/Max
findMin :: Set a -> a
O(log n). The minimal element of a set.
findMax :: Set a -> a
O(log n). The maximal element of a set.
deleteMin :: Set a -> Set a
O(log n). Delete the minimal element.
deleteMax :: Set a -> Set a
O(log n). Delete the maximal element.
deleteFindMin :: Set a -> (a, Set a)
O(log n). Delete and find the minimal element.
deleteFindMax :: Set a -> (a, Set a)
O(log n). Delete and find the maximal element.
Conversion
List
elems :: Set a -> [a]
O(n). The elements of a set.
toList :: Set a -> [a]
O(n). Convert the set to a list of elements.
fromList :: Ord a => [a] -> Set a
O(n*log n). Create a set from a list of elements.
Maybe
maybeToSet :: Maybe a -> Set a
Convert Maybe a to Set a; Nothing becomes the empty set
maybeSetToSet :: Maybe (Set a) -> Set a
Convert Maybe (Set a) to Set a; Nothing becomes the empty set
Ordered list
toAscList :: Set a -> [a]
O(n). Convert the set to an ascending list of elements.
fromAscList :: Eq a => [a] -> Set a
O(n). Build a map from an ascending list in linear time.
fromDistinctAscList :: [a] -> Set a
O(n). Build a set from an ascending list of distinct elements in linear time.
Debugging
showTree :: Show a => Set a -> String
O(n). Show the tree that implements the set. The tree is shown in a compressed, hanging format.
showTreeWith :: Show a => Bool -> Bool -> Set a -> String

O(n). The expression (showTreeWith hang wide map) shows the tree that implements the set. If hang is True, a hanging tree is shown otherwise a rotated tree is shown. If wide is true, an extra wide version is shown.

 Set> putStrLn $ showTreeWith True False $ fromDistinctAscList [1..5]
 4
 +--2
 |  +--1
 |  +--3
 +--5
 
 Set> putStrLn $ showTreeWith True True $ fromDistinctAscList [1..5]
 4
 |
 +--2
 |  |
 |  +--1
 |  |
 |  +--3
 |
 +--5
 
 Set> putStrLn $ showTreeWith False True $ fromDistinctAscList [1..5]
 +--5
 |
 4
 |
 |  +--3
 |  |
 +--2
    |
    +--1
valid :: Ord a => Set a -> Bool
O(n). Test if the internal set structure is valid.
Produced by Haddock version 0.6