-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Bitwise operations on bounded enumerations
--
-- Bitwise operations on bounded enumerations.
--
--
-- - Data.Enum.Set Constant-time sets using bit
-- flags.
-- - Data.Enum.Memo Constant-time lookup memoization for
-- functions on enumerated types.
--
@package bitwise-enum
@version 1.0.0.1
-- | Immutable lazy tables of functions over bounded enumerations. Function
-- calls are stored as thunks and not evaluated until accessed.
--
-- The underlying representation is an Array rather than a search
-- tree. This provides O(1) lookup but means that the range of
-- keys should not be very large, as in the case of an Int-like
-- type.
module Data.Enum.Memo
-- | Memoize a function with a single argument.
memoize :: forall k v. (Bounded k, Enum k) => (k -> v) -> k -> v
-- | Memoize a function with two arguments.
memoize2 :: forall k1 k2 v. (Bounded k1, Enum k1, Bounded k2, Enum k2) => (k1 -> k2 -> v) -> k1 -> k2 -> v
-- | Memoize a function with three arguments.
memoize3 :: forall k1 k2 k3 v. (Bounded k1, Enum k1, Bounded k2, Enum k2, Bounded k3, Enum k3) => (k1 -> k2 -> k3 -> v) -> k1 -> k2 -> k3 -> v
-- | Memoize a function with four arguments.
memoize4 :: forall k1 k2 k3 k4 v. (Bounded k1, Enum k1, Bounded k2, Enum k2, Bounded k3, Enum k3, Bounded k4, Enum k4) => (k1 -> k2 -> k3 -> k4 -> v) -> k1 -> k2 -> k3 -> k4 -> v
-- | Memoize a function with five arguments.
memoize5 :: forall k1 k2 k3 k4 k5 v. (Bounded k1, Enum k1, Bounded k2, Enum k2, Bounded k3, Enum k3, Bounded k4, Enum k4, Bounded k5, Enum k5) => (k1 -> k2 -> k3 -> k4 -> k5 -> v) -> k1 -> k2 -> k3 -> k4 -> k5 -> v
-- | 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.Base as E
--
-- data Foo = A | B | C | D | E | F | G | H deriving (Bounded, Enum, Eq, Ord, Show)
--
-- addFoos :: E.EnumSet Word Foo -> E.EnumSet Word Foo
-- addFoos = E.delete A . E.insert B
--
-- bar :: E.EnumSet Word Foo
-- bar = addFoos $ E.fromFoldable [A, C, E]
--
-- barHasB :: Bool
-- barHasB = E.member A bar
--
--
-- With -O or -O2, bar will compile to
-- GHC.Types.W# 22## and barHasA will compile to
-- GHC.Types.False.
--
-- For type EnumSet W E, W 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. EnumSet W 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 W. For
-- this reason, it is preferable for E to be a type that derives
-- Eq and Enum, and for W to have more bits than
-- the number of constructors of E.
--
-- For type EnumSet W E, if the highest fromEnum value
-- of E is 29, W should be Word, because it
-- always has at least 30 bits. Otherwise, options include Word32,
-- Word64, and the wide-word package's
-- Data.WideWord.Word128. Foreign types may also be used.
--
-- Data.Enum.Set provides an alternate type alias that moves the
-- underlying representation to an associated type token, so that e.g.
-- EnumSet Word64 MyEnum is replaced by EnumSet MyEnum,
-- and reexports this module with adjusted type signatures.
--
-- Note: complexity calculations assume that W implements
-- Bits with constant-time functions, as is the case with
-- Word etc. If this is not the case, the complexity of those
-- operations should be added to the complexity of EnumSet
-- functions.
module Data.Enum.Set.Base
-- | A set of values a with representation word,
-- implemented as bitwise operations.
data EnumSet word a
-- | O(1). The empty set.
empty :: forall w a. Bits w => EnumSet w a
-- | O(1). A set of one element.
singleton :: forall w a. (Bits w, Enum a) => a -> EnumSet w a
-- | O(n). Create a set from a finite foldable data structure.
fromFoldable :: forall f w a. (Foldable f, Bits w, Enum a) => f a -> EnumSet w a
-- | O(1). Add a value to the set.
insert :: forall w a. (Bits w, Enum a) => a -> EnumSet w a -> EnumSet w a
-- | O(1). Delete a value in the set.
delete :: forall w a. (Bits w, Enum a) => a -> EnumSet w a -> EnumSet w a
-- | O(1). Is the value a member of the set?
member :: forall w a. (Bits w, Enum a) => a -> EnumSet w a -> Bool
-- | O(1). Is the value not in the set?
notMember :: forall w a. (Bits w, Enum a) => a -> EnumSet w a -> Bool
-- | O(1). Is this the empty set?
null :: forall w a. Bits w => EnumSet w a -> Bool
-- | O(1). The number of elements in the set.
size :: forall w a. (Bits w, Num w) => EnumSet w a -> Int
-- | O(1). Is this a subset? (s1 isSubsetOf s2)
-- tells whether s1 is a subset of s2.
isSubsetOf :: forall w a. Bits w => EnumSet w a -> EnumSet w a -> Bool
-- | O(1). The union of two sets.
union :: forall w a. Bits w => EnumSet w a -> EnumSet w a -> EnumSet w a
-- | O(1). Difference between two sets.
difference :: forall w a. Bits w => EnumSet w a -> EnumSet w a -> EnumSet w a
-- | O(1). See difference.
(\\) :: forall w a. Bits w => EnumSet w a -> EnumSet w a -> EnumSet w a
infixl 9 \\
-- | O(1). Elements which are in either set, but not both.
symmetricDifference :: forall w a. Bits w => EnumSet w a -> EnumSet w a -> EnumSet w a
-- | O(1). The intersection of two sets.
intersection :: forall w a. Bits w => EnumSet w a -> EnumSet w a -> EnumSet w a
-- | O(n). Filter all elements that satisfy some predicate.
filter :: forall w a. (FiniteBits w, Num w, Enum a) => (a -> Bool) -> EnumSet w a -> EnumSet w a
-- | 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.
partition :: forall w a. (FiniteBits w, Num w, Enum a) => (a -> Bool) -> EnumSet w a -> (EnumSet w a, EnumSet w a)
-- | O(n). map f s is the set obtained by applying
-- 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.
map :: forall w a b. (FiniteBits w, Num w, Enum a, Enum b) => (a -> b) -> EnumSet w a -> EnumSet w b
-- | O(n). Apply map while converting the underlying
-- representation of the set to some other representation.
map' :: forall v w a b. (FiniteBits v, FiniteBits w, Num v, Num w, Enum a, Enum b) => (a -> b) -> EnumSet v a -> EnumSet w b
-- | O(n). Left fold.
foldl :: forall w a b. (FiniteBits w, Num w, Enum a) => (b -> a -> b) -> b -> EnumSet w a -> b
-- | O(n). Left fold with strict accumulator.
foldl' :: forall w a b. (FiniteBits w, Num w, Enum a) => (b -> a -> b) -> b -> EnumSet w a -> b
-- | O(n). Right fold.
foldr :: forall w a b. (FiniteBits w, Num w, Enum a) => (a -> b -> b) -> b -> EnumSet w a -> b
-- | O(n). Right fold with strict accumulator.
foldr' :: forall w a b. (FiniteBits w, Num w, Enum a) => (a -> b -> b) -> b -> EnumSet w a -> b
-- | O(n). Left fold on non-empty sets.
foldl1 :: forall w a. (FiniteBits w, Num w, Enum a) => (a -> a -> a) -> EnumSet w a -> a
-- | O(n). Left fold on non-empty sets with strict accumulator.
foldl1' :: forall w a. (FiniteBits w, Num w, Enum a) => (a -> a -> a) -> EnumSet w a -> a
-- | O(n). Right fold on non-empty sets.
foldr1 :: forall w a. (FiniteBits w, Num w, Enum a) => (a -> a -> a) -> EnumSet w a -> a
-- | O(n). Right fold on non-empty sets with strict accumulator.
foldr1' :: forall w a. (FiniteBits w, Num w, Enum a) => (a -> a -> a) -> EnumSet w a -> a
-- | O(n). Map each element of the structure to a monoid, and
-- combine the results.
foldMap :: forall m w a. (Monoid m, FiniteBits w, Num w, Enum a) => (a -> m) -> EnumSet w a -> m
traverse :: forall f w a. (Applicative f, FiniteBits w, Num w, Enum a) => (a -> f a) -> EnumSet w a -> f (EnumSet w a)
-- | O(n). Check if any element satisfies some predicate.
any :: forall w a. (FiniteBits w, Num w, Enum a) => (a -> Bool) -> EnumSet w a -> Bool
-- | O(n). Check if all elements satisfy some predicate.
all :: forall w a. (FiniteBits w, Num w, Enum a) => (a -> Bool) -> EnumSet w a -> Bool
-- | O(1). The minimal element of a non-empty set.
minimum :: forall w a. (FiniteBits w, Num w, Enum a) => EnumSet w a -> a
-- | O(1). The maximal element of a non-empty set.
maximum :: forall w a. (FiniteBits w, Num w, Enum a) => EnumSet w a -> a
-- | O(1). Delete the minimal element.
deleteMin :: forall w a. (FiniteBits w, Num w) => EnumSet w a -> EnumSet w a
-- | O(1). Delete the maximal element.
deleteMax :: forall w a. (FiniteBits w, Num w) => EnumSet w a -> EnumSet w a
-- | O(1). Retrieves the minimal element of the set, and the set
-- stripped of that element, or Nothing if passed an empty set.
minView :: forall w a. (FiniteBits w, Num w, Enum a) => EnumSet w a -> Maybe (a, EnumSet w a)
-- | O(1). Retrieves the maximal element of the set, and the set
-- stripped of that element, or Nothing if passed an empty set.
maxView :: forall w a. (FiniteBits w, Num w, Enum a) => EnumSet w a -> Maybe (a, EnumSet w a)
-- | O(n). Convert the set to a list of values.
toList :: forall w a. (FiniteBits w, Num w, Enum a) => EnumSet w a -> [a]
-- | O(1). Convert a representation into an EnumSet.
-- Intended for use with foreign types.
fromRaw :: forall w a. w -> EnumSet w a
instance forall word k (a :: k). Data.Primitive.Types.Prim word => Data.Vector.Unboxed.Base.Unbox (Data.Enum.Set.Base.EnumSet word a)
instance forall word k (a :: k). Data.Primitive.Types.Prim word => Data.Primitive.Types.Prim (Data.Enum.Set.Base.EnumSet word a)
instance forall word k (a :: k). Control.DeepSeq.NFData word => Control.DeepSeq.NFData (Data.Enum.Set.Base.EnumSet word a)
instance forall word k (a :: k). Foreign.Storable.Storable word => Foreign.Storable.Storable (Data.Enum.Set.Base.EnumSet word a)
instance forall word k (a :: k). (Data.Typeable.Internal.Typeable a, Data.Typeable.Internal.Typeable k, Data.Data.Data word) => Data.Data.Data (Data.Enum.Set.Base.EnumSet word a)
instance forall word k (a :: k). GHC.Classes.Ord word => GHC.Classes.Ord (Data.Enum.Set.Base.EnumSet word a)
instance forall word k (a :: k). GHC.Classes.Eq word => GHC.Classes.Eq (Data.Enum.Set.Base.EnumSet word a)
instance forall k word (a :: k). Data.Primitive.Types.Prim word => Data.Vector.Generic.Mutable.Base.MVector Data.Vector.Unboxed.Base.MVector (Data.Enum.Set.Base.EnumSet word a)
instance forall k word (a :: k). Data.Primitive.Types.Prim word => Data.Vector.Generic.Base.Vector Data.Vector.Unboxed.Base.Vector (Data.Enum.Set.Base.EnumSet word a)
instance forall k w (a :: k). Data.Bits.Bits w => GHC.Base.Semigroup (Data.Enum.Set.Base.EnumSet w a)
instance forall k w (a :: k). Data.Bits.Bits w => GHC.Base.Monoid (Data.Enum.Set.Base.EnumSet w a)
instance (Data.Bits.Bits w, GHC.Enum.Enum a) => Data.MonoTraversable.MonoPointed (Data.Enum.Set.Base.EnumSet w a)
instance (Data.Bits.FiniteBits w, GHC.Num.Num w, GHC.Enum.Enum a) => GHC.Exts.IsList (Data.Enum.Set.Base.EnumSet w a)
instance (Data.Bits.FiniteBits w, GHC.Num.Num w, GHC.Enum.Enum a, Data.Aeson.Types.ToJSON.ToJSON a) => Data.Aeson.Types.ToJSON.ToJSON (Data.Enum.Set.Base.EnumSet w a)
instance (Data.Bits.FiniteBits w, GHC.Num.Num w, GHC.Enum.Enum a) => Data.MonoTraversable.MonoFunctor (Data.Enum.Set.Base.EnumSet w a)
instance (Data.Bits.FiniteBits w, GHC.Num.Num w, GHC.Enum.Enum a) => Data.MonoTraversable.MonoFoldable (Data.Enum.Set.Base.EnumSet w a)
instance (Data.Bits.FiniteBits w, GHC.Num.Num w, GHC.Enum.Enum a) => Data.MonoTraversable.GrowingAppend (Data.Enum.Set.Base.EnumSet w a)
instance (Data.Bits.FiniteBits w, GHC.Num.Num w, GHC.Enum.Enum a) => Data.MonoTraversable.MonoTraversable (Data.Enum.Set.Base.EnumSet w a)
instance (Data.Bits.FiniteBits w, GHC.Num.Num w, GHC.Classes.Eq a, GHC.Enum.Enum a) => Data.Containers.SetContainer (Data.Enum.Set.Base.EnumSet w a)
instance (Data.Bits.FiniteBits w, GHC.Num.Num w, GHC.Classes.Eq a, GHC.Enum.Enum a) => Data.Containers.IsSet (Data.Enum.Set.Base.EnumSet w a)
instance (Data.Bits.FiniteBits w, GHC.Num.Num w, GHC.Enum.Enum x, GHC.Show.Show x) => GHC.Show.Show (Data.Enum.Set.Base.EnumSet w x)
instance (Data.Bits.Bits w, GHC.Num.Num w, GHC.Enum.Enum x, GHC.Read.Read x) => GHC.Read.Read (Data.Enum.Set.Base.EnumSet w x)
-- | 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. 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.
module Data.Enum.Set
class (Enum a, FiniteBits (EnumSetRep a), Num (EnumSetRep a)) => AsEnumSet a where {
type family EnumSetRep a;
type EnumSetRep a = Word;
}
type EnumSet a = EnumSet (EnumSetRep a) a
-- | O(1). The empty set.
empty :: forall a. AsEnumSet a => EnumSet a
-- | O(1). A set of one element.
singleton :: forall a. AsEnumSet a => a -> EnumSet a
-- | O(n). Create a set from a finite foldable data structure.
fromFoldable :: forall f a. (Foldable f, AsEnumSet a) => f a -> EnumSet a
-- | O(1). Add a value to the set.
insert :: forall a. AsEnumSet a => a -> EnumSet a -> EnumSet a
-- | O(1). Delete a value in the set.
delete :: forall a. AsEnumSet a => a -> EnumSet a -> EnumSet a
-- | O(1). Is the value a member of the set?
member :: forall a. AsEnumSet a => a -> EnumSet a -> Bool
-- | O(1). Is the value not in the set?
notMember :: forall a. AsEnumSet a => a -> EnumSet a -> Bool
-- | O(1). Is this the empty set?
null :: forall a. AsEnumSet a => EnumSet a -> Bool
-- | O(1). The number of elements in the set.
size :: forall a. AsEnumSet a => EnumSet a -> Int
-- | O(1). Is this a subset? (s1 isSubsetOf s2)
-- tells whether s1 is a subset of s2.
isSubsetOf :: forall a. AsEnumSet a => EnumSet a -> EnumSet a -> Bool
-- | O(1). The union of two sets.
union :: forall a. AsEnumSet a => EnumSet a -> EnumSet a -> EnumSet a
-- | O(1). Difference between two sets.
difference :: forall a. AsEnumSet a => EnumSet a -> EnumSet a -> EnumSet a
-- | O(1). See difference.
(\\) :: forall a. AsEnumSet a => EnumSet a -> EnumSet a -> EnumSet a
infixl 9 \\
-- | O(1). Elements which are in either set, but not both.
symmetricDifference :: forall a. AsEnumSet a => EnumSet a -> EnumSet a -> EnumSet a
-- | O(1). The intersection of two sets.
intersection :: forall a. AsEnumSet a => EnumSet a -> EnumSet a -> EnumSet a
-- | O(n). Filter all elements that satisfy some predicate.
filter :: forall a. AsEnumSet a => (a -> Bool) -> EnumSet a -> EnumSet a
-- | 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.
partition :: forall a. AsEnumSet a => (a -> Bool) -> EnumSet a -> (EnumSet a, EnumSet a)
-- | O(n). map f s is the set obtained by applying
-- 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
map :: forall a b. (AsEnumSet a, AsEnumSet b) => (a -> b) -> EnumSet a -> EnumSet b
-- | O(n). Left fold.
foldl :: forall a b. AsEnumSet a => (b -> a -> b) -> b -> EnumSet a -> b
-- | O(n). Left fold with strict accumulator.
foldl' :: forall a b. AsEnumSet a => (b -> a -> b) -> b -> EnumSet a -> b
-- | O(n). Right fold.
foldr :: forall a b. AsEnumSet a => (a -> b -> b) -> b -> EnumSet a -> b
-- | O(n). Right fold with strict accumulator.
foldr' :: forall a b. AsEnumSet a => (a -> b -> b) -> b -> EnumSet a -> b
-- | O(n). Left fold on non-empty sets.
foldl1 :: forall a. AsEnumSet a => (a -> a -> a) -> EnumSet a -> a
-- | O(n). Left fold on non-empty sets with strict accumulator.
foldl1' :: forall a. AsEnumSet a => (a -> a -> a) -> EnumSet a -> a
-- | O(n). Right fold on non-empty sets.
foldr1 :: forall a. AsEnumSet a => (a -> a -> a) -> EnumSet a -> a
-- | O(n). Right fold on non-empty sets with strict accumulator.
foldr1' :: forall a. AsEnumSet a => (a -> a -> a) -> EnumSet a -> a
-- | O(n). Map each element of the structure to a monoid, and
-- combine the results.
foldMap :: forall m a. (Monoid m, AsEnumSet a) => (a -> m) -> EnumSet a -> m
traverse :: forall f a. (Applicative f, AsEnumSet a) => (a -> f a) -> EnumSet a -> f (EnumSet a)
-- | O(n). Check if any element satisfies some predicate.
any :: forall a. AsEnumSet a => (a -> Bool) -> EnumSet a -> Bool
-- | O(n). Check if all elements satisfy some predicate.
all :: forall a. AsEnumSet a => (a -> Bool) -> EnumSet a -> Bool
-- | O(1). The minimal element of a non-empty set.
minimum :: forall a. AsEnumSet a => EnumSet a -> a
-- | O(1). The maximal element of a non-empty set.
maximum :: forall a. AsEnumSet a => EnumSet a -> a
-- | O(1). Delete the minimal element.
deleteMin :: forall a. AsEnumSet a => EnumSet a -> EnumSet a
-- | O(1). Delete the maximal element.
deleteMax :: forall a. AsEnumSet a => EnumSet a -> EnumSet a
-- | O(1). Retrieves the minimal element of the set, and the set
-- stripped of that element, or Nothing if passed an empty set.
minView :: forall a. AsEnumSet a => EnumSet a -> Maybe (a, EnumSet a)
-- | O(1). Retrieves the maximal element of the set, and the set
-- stripped of that element, or Nothing if passed an empty set.
maxView :: forall a. AsEnumSet a => EnumSet a -> Maybe (a, EnumSet a)
-- | O(n). Convert the set to a list of values.
toList :: forall a. AsEnumSet a => EnumSet a -> [a]
-- | O(1). Convert a representation into an EnumSet.
-- Intended for use with foreign types.
fromRaw :: forall a. AsEnumSet a => EnumSetRep a -> EnumSet a