| 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