Portability | GHC |
---|---|

Stability | experimental |

Maintainer | superbobry@gmail.com |

Safe Haskell | None |

A space-efficient implementation of set data structure for enumerated data types.

*Note*: Read below the synopsis for important notes on the use of
this module.

This module is intended to be imported `qualified`

, to avoid name
clashes with Prelude functions, e.g.

import Data.BitSet.Word (BitSet) import qualified Data.BitSet.Word as BS

The implementation uses `Word`

as underlying container, thus the
maximum number of elements you can store in this bit set is bounded
by the number of bits in `Word`

data type. However, due to native bitwise
operations Data.BitSet.Word is significantly faster then Data.Set
on all operations.

- type BitSet = BitSet Word
- (\\) :: BitSet a -> BitSet a -> BitSet a
- empty :: Enum a => BitSet a
- singleton :: Enum a => a -> BitSet a
- insert :: Enum a => a -> BitSet a -> BitSet a
- delete :: Enum a => a -> BitSet a -> BitSet a
- null :: BitSet a -> Bool
- size :: BitSet a -> Int
- member :: Enum a => a -> BitSet a -> Bool
- notMember :: Enum a => a -> BitSet a -> Bool
- isSubsetOf :: BitSet a -> BitSet a -> Bool
- isProperSubsetOf :: BitSet a -> BitSet a -> Bool
- union :: BitSet a -> BitSet a -> BitSet a
- difference :: BitSet a -> BitSet a -> BitSet a
- intersection :: BitSet a -> BitSet a -> BitSet a
- map :: (Enum a, Enum b) => (a -> b) -> BitSet a -> BitSet b
- foldl' :: Enum a => (b -> a -> b) -> b -> BitSet a -> b
- foldr :: Enum a => (a -> b -> b) -> b -> BitSet a -> b
- filter :: Enum a => (a -> Bool) -> BitSet a -> BitSet a
- toList :: Enum a => BitSet a -> [a]
- fromList :: Enum a => [a] -> BitSet a

# Bit set type

# Operators

# Construction

# Query

isSubsetOf :: BitSet a -> BitSet a -> BoolSource

*O(1)*. Is this a subset? (`s1 isSubsetOf s2`

) tells whether
`s1`

is a subset of `s2`

.

isProperSubsetOf :: BitSet a -> BitSet a -> BoolSource

*O(1)*. Is this a proper subset? (ie. a subset but not equal).

# Combine

difference :: BitSet a -> BitSet a -> BitSet aSource

*O(1)*. Difference of two bit sets.

intersection :: BitSet a -> BitSet a -> BitSet aSource

*O(1)*. The intersection of two bit sets.

# Transformations

map :: (Enum a, Enum b) => (a -> b) -> BitSet a -> BitSet bSource

*O(n)* Transform this bit set by applying a function to every value.
Resulting bit set may be smaller then the original.

# Folds

foldl' :: Enum a => (b -> a -> b) -> b -> BitSet a -> bSource

*O(n)* Reduce this bit set by applying a binary function to all
elements, using the given starting value. Each application of the
operator is evaluated before before using the result in the next
application. This function is strict in the starting value.

foldr :: Enum a => (a -> b -> b) -> b -> BitSet a -> bSource

*O(n)* Reduce this bit set by applying a binary function to all
elements, using the given starting value.

# Filter

filter :: Enum a => (a -> Bool) -> BitSet a -> BitSet aSource

*O(n)* Filter this bit set by retaining only elements satisfying a
predicate.