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.Generic (BitSet) import qualified Data.BitSet.Generic as BS

The implementation is abstract with respect to container type, so any
numeric type with `Bits`

instance can be used as a container. However,
independent of container choice, the maximum number of elements in a
bit set is bounded by `maxBound :: Int`

.

- newtype BitSet c a = BitSet {
- getBits :: c

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

# Bit set type

A bit set with unspecified container type.

# Operators

# Construction

insert :: (Enum a, Bits c) => a -> BitSet c a -> BitSet c aSource

*O(d)*. Insert an item into the bit set.

delete :: (Enum a, Bits c) => a -> BitSet c a -> BitSet c aSource

*O(d)*. Delete an item from the bit set.

# Query

member :: (Enum a, Bits c) => a -> BitSet c a -> BoolSource

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

notMember :: (Enum a, Bits c) => a -> BitSet c a -> BoolSource

*O(d)*. Ask whether the item is not in the bit set.

isSubsetOf :: (Bits c, Eq c) => BitSet c a -> BitSet c a -> BoolSource

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

) tells whether
`isSubsetOf`

s2`s1`

is a subset of `s2`

.

isProperSubsetOf :: (Bits c, Eq c) => BitSet c a -> BitSet c a -> BoolSource

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

# Combine

union :: Bits c => BitSet c a -> BitSet c a -> BitSet c aSource

*O(max(m, n))*. The union of two bit sets.

difference :: Bits c => BitSet c a -> BitSet c a -> BitSet c aSource

*O(max(m, n))*. Difference of two bit sets.

intersection :: Bits c => BitSet c a -> BitSet c a -> BitSet c aSource

*O(max(m, n))*. The intersection of two bit sets.

# Transformations

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

*O(d * 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, Bits c) => (b -> a -> b) -> b -> BitSet c a -> bSource

*O(d * 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, Bits c) => (a -> b -> b) -> b -> BitSet c a -> bSource

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

# Filter

filter :: (Enum a, Bits c, Num c) => (a -> Bool) -> BitSet c a -> BitSet c aSource

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