Safe Haskell	None
Language	Haskell2010

Data.Enum.Set

Contents

Set type
Construction
Insertion
Deletion
Query
Combine
Filter
Map
Folds
- Special folds
Min/Max
Conversion

Description

Efficient sets over bounded enumerations, using bitwise operations based on containers and EdisonCore. In many cases, EnumSets may be optimised away entirely by constant folding at compile-time. For example, in the following code:

import Data.Enum.Set as E

data Foo = A | B | C | D | E | F | G | H deriving (Bounded, Enum, Eq, Ord)

instance E.AsEnumSet Foo

addFoos :: E.EnumSet Foo -> E.EnumSet Foo
addFoos = E.delete A . E.insert B

bar :: E.EnumSet Foo
bar = addFoos $ E.fromFoldable [A, C, E]

barHasA :: Bool
barHasA = E.member A bar

With -O or -O2, bar will compile to GHC.Types.W# 22## and barHasA will compile to GHC.Types.False.

By default, Words are used as the representation. Other representations may be chosen in the class instance:

{-# LANGUAGE TypeFamilies #-}

import Data.Enum.Set as E
import Data.Word (Word64)

data Foo = A | B | C | D | E | F | G | H deriving (Bounded, Enum, Eq, Ord, Show)

instance E.AsEnumSet Foo where
    type EnumSetRep Foo = Word64

For type EnumSet E, EnumSetRep E should be a Word-like type that implements Bits and Num, and E should be a type that implements Eq and Enum equivalently and is a bijection to Int over its range. EnumSet E can only store a value of E if the result of applying fromEnum to the value is positive and less than the number of bits in EnumSetRep E. For this reason, it is preferable for E to be a type that derives Eq and Enum, and for EnumSetRep E to have more bits than the number of constructors of E.

If the highest fromEnum value of E is 29, EnumSetRep E should be Word, because it always has at least 30 bits. This is the default implementation. Otherwise, options include Word32, Word64, and the wide-word package's Data.WideWord.Word128. Foreign types may also be used.

Note: complexity calculations assume that EnumSetRep E implements Bits with constant-time functions, as is the case with Word etc. Otherwise, the complexity of those operations should be added to the complexity of EnumSet functions.

Synopsis

class (Enum a, FiniteBits (EnumSetRep a), Num (EnumSetRep a)) => AsEnumSet a where
- type EnumSetRep a
type EnumSet a = EnumSet (EnumSetRep a) a
empty :: AsEnumSet a => EnumSet a
singleton :: AsEnumSet a => a -> EnumSet a
fromFoldable :: (Foldable f, AsEnumSet a) => f a -> EnumSet a
insert :: AsEnumSet a => a -> EnumSet a -> EnumSet a
delete :: AsEnumSet a => a -> EnumSet a -> EnumSet a
member :: AsEnumSet a => a -> EnumSet a -> Bool
notMember :: AsEnumSet a => a -> EnumSet a -> Bool
null :: AsEnumSet a => EnumSet a -> Bool
size :: AsEnumSet a => EnumSet a -> Int
isSubsetOf :: AsEnumSet a => EnumSet a -> EnumSet a -> Bool
union :: AsEnumSet a => EnumSet a -> EnumSet a -> EnumSet a
difference :: AsEnumSet a => EnumSet a -> EnumSet a -> EnumSet a
(\\) :: AsEnumSet a => EnumSet a -> EnumSet a -> EnumSet a
symmetricDifference :: AsEnumSet a => EnumSet a -> EnumSet a -> EnumSet a
intersection :: AsEnumSet a => EnumSet a -> EnumSet a -> EnumSet a
filter :: AsEnumSet a => (a -> Bool) -> EnumSet a -> EnumSet a
partition :: AsEnumSet a => (a -> Bool) -> EnumSet a -> (EnumSet a, EnumSet a)
map :: (AsEnumSet a, AsEnumSet b) => (a -> b) -> EnumSet a -> EnumSet b
foldl :: AsEnumSet a => (b -> a -> b) -> b -> EnumSet a -> b
foldl' :: AsEnumSet a => (b -> a -> b) -> b -> EnumSet a -> b
foldr :: AsEnumSet a => (a -> b -> b) -> b -> EnumSet a -> b
foldr' :: AsEnumSet a => (a -> b -> b) -> b -> EnumSet a -> b
foldl1 :: AsEnumSet a => (a -> a -> a) -> EnumSet a -> a
foldl1' :: AsEnumSet a => (a -> a -> a) -> EnumSet a -> a
foldr1 :: AsEnumSet a => (a -> a -> a) -> EnumSet a -> a
foldr1' :: AsEnumSet a => (a -> a -> a) -> EnumSet a -> a
foldMap :: (Monoid m, AsEnumSet a) => (a -> m) -> EnumSet a -> m
traverse :: (Applicative f, AsEnumSet a) => (a -> f a) -> EnumSet a -> f (EnumSet a)
any :: AsEnumSet a => (a -> Bool) -> EnumSet a -> Bool
all :: AsEnumSet a => (a -> Bool) -> EnumSet a -> Bool
minimum :: AsEnumSet a => EnumSet a -> a
maximum :: AsEnumSet a => EnumSet a -> a
deleteMin :: AsEnumSet a => EnumSet a -> EnumSet a
deleteMax :: AsEnumSet a => EnumSet a -> EnumSet a
minView :: AsEnumSet a => EnumSet a -> Maybe (a, EnumSet a)
maxView :: AsEnumSet a => EnumSet a -> Maybe (a, EnumSet a)
toList :: AsEnumSet a => EnumSet a -> [a]
fromRaw :: AsEnumSet a => EnumSetRep a -> EnumSet a
toRaw :: AsEnumSet a => EnumSet a -> EnumSetRep a

Documentation

class (Enum a, FiniteBits (EnumSetRep a), Num (EnumSetRep a)) => AsEnumSet a Source #

Associated Types

type EnumSetRep a Source #

type EnumSetRep a = Word

Set type

type EnumSet a = EnumSet (EnumSetRep a) a Source #

Construction

empty :: AsEnumSet a => EnumSet a Source #

O(1). The empty set.

singleton :: AsEnumSet a => a -> EnumSet a Source #

O(1). A set of one element.

fromFoldable :: (Foldable f, AsEnumSet a) => f a -> EnumSet a Source #

O(n). Create a set from a finite foldable data structure.

Insertion

insert :: AsEnumSet a => a -> EnumSet a -> EnumSet a Source #

O(1). Add a value to the set.

Deletion

delete :: AsEnumSet a => a -> EnumSet a -> EnumSet a Source #

O(1). Delete a value in the set.

Query

member :: AsEnumSet a => a -> EnumSet a -> Bool Source #

O(1). Is the value a member of the set?

notMember :: AsEnumSet a => a -> EnumSet a -> Bool Source #

O(1). Is the value not in the set?

null :: AsEnumSet a => EnumSet a -> Bool Source #

O(1). Is this the empty set?

size :: AsEnumSet a => EnumSet a -> Int Source #

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

isSubsetOf :: AsEnumSet a => EnumSet a -> EnumSet a -> Bool Source #

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

Combine

union :: AsEnumSet a => EnumSet a -> EnumSet a -> EnumSet a Source #

O(1). The union of two sets.

difference :: AsEnumSet a => EnumSet a -> EnumSet a -> EnumSet a Source #

O(1). Difference between two sets.

(\\) :: AsEnumSet a => EnumSet a -> EnumSet a -> EnumSet a infixl 9 Source #

O(1). See difference.

symmetricDifference :: AsEnumSet a => EnumSet a -> EnumSet a -> EnumSet a Source #

O(1). Elements which are in either set, but not both.

intersection :: AsEnumSet a => EnumSet a -> EnumSet a -> EnumSet a Source #

O(1). The intersection of two sets.

Filter

filter :: AsEnumSet a => (a -> Bool) -> EnumSet a -> EnumSet a Source #

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

partition :: AsEnumSet a => (a -> Bool) -> EnumSet a -> (EnumSet a, EnumSet a) Source #

O(n). Partition the set according to some predicate. The first set contains all elements that satisfy the predicate, the second all elements that fail the predicate.