Portability | portable |
---|---|

Stability | provisional |

Maintainer | libraries@haskell.org |

An efficient implementation of integer sets.

Since many function names (but not the type name) clash with
Prelude names, this module is usually imported `qualified`

, e.g.

import Data.IntSet (IntSet) import qualified Data.IntSet as IntSet

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://citeseer.ist.psu.edu/okasaki98fast.html - 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).

- data IntSet
- (\\) :: IntSet -> IntSet -> IntSet
- null :: IntSet -> Bool
- size :: IntSet -> Int
- member :: Int -> IntSet -> Bool
- notMember :: 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)
- findMin :: IntSet -> Int
- findMax :: IntSet -> Int
- deleteMin :: IntSet -> IntSet
- deleteMax :: IntSet -> IntSet
- deleteFindMin :: IntSet -> (Int, IntSet)
- deleteFindMax :: IntSet -> (Int, IntSet)
- maxView :: IntSet -> Maybe (Int, IntSet)
- minView :: IntSet -> Maybe (Int, 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

A set of integers.

# Operators

# Query

isSubsetOf :: IntSet -> IntSet -> BoolSource

*O(n+m)*. Is this a subset?
`(s1 `

tells whether `isSubsetOf`

s2)`s1`

is a subset of `s2`

.

isProperSubsetOf :: IntSet -> IntSet -> BoolSource

*O(n+m)*. Is this a proper subset? (ie. a subset but not equal).

# Construction

insert :: Int -> IntSet -> IntSetSource

*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 -> IntSetSource

*O(min(n,W))*. Delete a value in the set. Returns the
original set when the value was not present.

# Combine

difference :: IntSet -> IntSet -> IntSetSource

*O(n+m)*. Difference between two sets.

intersection :: IntSet -> IntSet -> IntSetSource

*O(n+m)*. The intersection of two sets.

# Filter

filter :: (Int -> Bool) -> IntSet -> IntSetSource

*O(n)*. Filter all elements that satisfy some predicate.

partition :: (Int -> Bool) -> IntSet -> (IntSet, IntSet)Source

*O(n)*. partition the set according to some predicate.

split :: Int -> IntSet -> (IntSet, IntSet)Source

*O(min(n,W))*. The expression (

) is a pair `split`

x set`(set1,set2)`

where `set1`

comprises the elements of `set`

less than `x`

and `set2`

comprises the elements of `set`

greater than `x`

.

split 3 (fromList [1..5]) == (fromList [1,2], fromList [4,5])

splitMember :: Int -> IntSet -> (IntSet, Bool, IntSet)Source

*O(min(n,W))*. Performs a `split`

but also returns whether the pivot
element was found in the original set.

# Min/Max

deleteFindMin :: IntSet -> (Int, IntSet)Source

*O(min(n,W))*. Delete and find the minimal element.

deleteFindMin set = (findMin set, deleteMin set)

deleteFindMax :: IntSet -> (Int, IntSet)Source

*O(min(n,W))*. Delete and find the maximal element.

deleteFindMax set = (findMax set, deleteMax set)

maxView :: IntSet -> Maybe (Int, IntSet)Source

*O(min(n,W))*. Retrieves the maximal key of the set, and the set
stripped of that element, or `Nothing`

if passed an empty set.

minView :: IntSet -> Maybe (Int, IntSet)Source

*O(min(n,W))*. Retrieves the minimal key of the set, and the set
stripped of that element, or `Nothing`

if passed an empty set.

# Map

map :: (Int -> Int) -> IntSet -> IntSetSource

*O(n*min(n,W))*.

is the set obtained by applying `map`

f s`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 -> bSource

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

sum set == fold (+) 0 set elems set == fold (:) [] set

# Conversion

## List

## Ordered list

fromAscList :: [Int] -> IntSetSource

*O(n)*. Build a set from an ascending list of elements.
*The precondition (input list is ascending) is not checked.*

fromDistinctAscList :: [Int] -> IntSetSource

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

# Debugging

showTree :: IntSet -> StringSource

*O(n)*. Show the tree that implements the set. The tree is shown
in a compressed, hanging format.

showTreeWith :: Bool -> Bool -> IntSet -> StringSource

*O(n)*. The expression (

) shows
the tree that implements the set. If `showTreeWith`

hang wide map`hang`

is
`True`

, a *hanging* tree is shown otherwise a rotated tree is shown. If
`wide`

is `True`

, an extra wide version is shown.