Portability	GHC
Stability	experimental
Maintainer	[email protected]
Safe Haskell	None

Data.BitSet.Word

Contents

Bit set type
Operators
Construction
Query
Combine
Transformations
Folds
Filter
Lists

Description

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.

Synopsis

Bit set type

type BitSet = BitSet Word Source

Operators

(\\) :: BitSet a -> BitSet a -> BitSet aSource

O(1). See difference.

Construction

empty :: Enum a => BitSet aSource

The empty bit set.

singleton :: Enum a => a -> BitSet aSource

O(1). Create a singleton set.

insert :: Enum a => a -> BitSet a -> BitSet aSource

O(1). Insert an item into the bit set.

delete :: Enum a => a -> BitSet a -> BitSet aSource

O(1). Delete an item from the bit set.

Query

null :: BitSet a -> Bool Source

O(1). Is the bit set empty?

size :: BitSet a -> Int Source

O(1). The number of elements in the bit set.

member :: Enum a => a -> BitSet a -> Bool Source

O(1). Ask whether the item is in the bit set.

notMember :: Enum a => a -> BitSet a -> Bool Source

O(1). Ask whether the item is in the bit set.

isSubsetOf :: BitSet a -> BitSet a -> Bool Source

O(1). Is this a subset? (s1 isSubsetOf s2) tells whether s1 is a subset of s2.

isProperSubsetOf :: BitSet a -> BitSet a -> Bool Source

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

Combine

union :: BitSet a -> BitSet a -> BitSet aSource

O(1). The union of two bit sets.

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.

Lists

toList :: Enum a => BitSet a -> [a]Source

O(n). Convert the bit set set to a list of elements.

fromList :: Enum a => [a] -> BitSet aSource

O(n). Make a bit set from a list of elements.