| Haskell Hierarchical Libraries (base package) | Contents | Index
Data.IntSet |
Portability | portable
Stability | provisional
Maintainer | libraries@haskell.org
Contents
Set type Operators Query Construction Combine Filter Map Fold Conversion List Ordered list Debugging
Description
An efficient implementation of integer sets. This module is intended to be imported `qualified`, to avoid name clashes with Prelude functions. eg.
      import Data.IntSet as Set
The implementation is based on big-endian patricia trees. This data structure performs especially well on binary operations like `union` and `intersection`. However, my benchmarks show that it is also (much) faster on insertions and deletions when compared to a generic size-balanced set implementation (see Data.Set). Chris Okasaki and Andy Gill, "Fast Mergeable Integer Maps", Workshop on ML, September 1998, pages 77-86, http://www.cse.ogi.edu/~andy/pub/finite.htm D.R. Morrison, "PATRICIA -- Practical Algorithm To Retrieve Information Coded In Alphanumeric", Journal of the ACM, 15(4), October 1968, pages 514-534. Many operations have a worst-case complexity of O(min(n,W)). This means that the operation can become linear in the number of elements with a maximum of W -- the number of bits in an `Int` (32 or 64).
Synopsis
data IntSet
(\\) :: IntSet -> IntSet -> IntSet
null :: IntSet -> Bool
size :: IntSet -> Int
member :: Int -> IntSet -> Bool
isSubsetOf :: IntSet -> IntSet -> Bool
isProperSubsetOf :: IntSet -> IntSet -> Bool
empty :: IntSet
singleton :: Int -> IntSet
insert :: Int -> IntSet -> IntSet
delete :: Int -> IntSet -> IntSet
union :: IntSet -> IntSet -> IntSet
unions :: [IntSet] -> IntSet
difference :: IntSet -> IntSet -> IntSet
intersection :: IntSet -> IntSet -> IntSet
filter :: (Int -> Bool) -> IntSet -> IntSet
partition :: (Int -> Bool) -> IntSet -> (IntSet, IntSet)
split :: Int -> IntSet -> (IntSet, IntSet)
splitMember :: Int -> IntSet -> (IntSet, Bool, IntSet)
map :: (Int -> Int) -> IntSet -> IntSet
fold :: (Int -> b -> b) -> b -> IntSet -> b
elems :: IntSet -> [Int]
toList :: IntSet -> [Int]
fromList :: [Int] -> IntSet
toAscList :: IntSet -> [Int]
fromAscList :: [Int] -> IntSet
fromDistinctAscList :: [Int] -> IntSet
showTree :: IntSet -> String
showTreeWith :: Bool -> Bool -> IntSet -> String
Set type
data IntSet
A set of integers.
Instances
Data IntSet
Eq IntSet
Monoid IntSet
Ord IntSet
Show IntSet
Typeable IntSet
Operators
(\\) :: IntSet -> IntSet -> IntSet
O(n+m). See `difference`.
Query
null :: IntSet -> Bool
O(1). Is the set empty?
size :: IntSet -> Int
O(n). Cardinality of the set.
member :: Int -> IntSet -> Bool
O(min(n,W)). Is the value a member of the set?
isSubsetOf :: IntSet -> IntSet -> Bool
O(n+m). Is this a subset? `(s1 `isSubsetOf` s2)` tells whether `s1` is a subset of `s2`.
isProperSubsetOf :: IntSet -> IntSet -> Bool
O(n+m). Is this a proper subset? (ie. a subset but not equal).
Construction
empty :: IntSet
O(1). The empty set.
singleton :: Int -> IntSet
O(1). A set of one element.
insert :: Int -> IntSet -> IntSet
O(min(n,W)). Add a value to the set. When the value is already an element of the set, it is replaced by the new one, ie. `insert` is left-biased.
delete :: Int -> IntSet -> IntSet
O(min(n,W)). Delete a value in the set. Returns the original set when the value was not present.
Combine
union :: IntSet -> IntSet -> IntSet
O(n+m). The union of two sets.
unions :: [IntSet] -> IntSet
The union of a list of sets.
difference :: IntSet -> IntSet -> IntSet
O(n+m). Difference between two sets.
intersection :: IntSet -> IntSet -> IntSet
O(n+m). The intersection of two sets.
Filter
filter :: (Int -> Bool) -> IntSet -> IntSet
O(n). Filter all elements that satisfy some predicate.
partition :: (Int -> Bool) -> IntSet -> (IntSet, IntSet)
O(n). partition the set according to some predicate.
split :: Int -> IntSet -> (IntSet, IntSet)
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`.
     split 3 (fromList [1..5]) == (fromList [1,2], fromList [3,4])
splitMember :: Int -> IntSet -> (IntSet, Bool, IntSet)
O(log n). Performs a `split` but also returns whether the pivot element was found in the original set.
Map
map :: (Int -> Int) -> IntSet -> IntSet
O(n*min(n,W)). ``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`
Fold
fold :: (Int -> b -> b) -> b -> IntSet -> b
O(n). Fold over the elements of a set in an unspecified order.
     sum set   == fold (+) 0 set
     elems set == fold (:) [] set
Conversion
List
elems :: IntSet -> [Int]
O(n). The elements of a set. (For sets, this is equivalent to toList)
toList :: IntSet -> [Int]
O(n). Convert the set to a list of elements.
fromList :: [Int] -> IntSet
O(n*min(n,W)). Create a set from a list of integers.
Ordered list
toAscList :: IntSet -> [Int]
O(n). Convert the set to an ascending list of elements.
fromAscList :: [Int] -> IntSet
O(n*min(n,W)). Build a set from an ascending list of elements.
fromDistinctAscList :: [Int] -> IntSet
O(n*min(n,W)). Build a set from an ascending list of distinct elements.
Debugging
showTree :: IntSet -> String
O(n). Show the tree that implements the set. The tree is shown in a compressed, hanging format.
showTreeWith :: Bool -> Bool -> IntSet -> 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.
Produced by Haddock version 0.7