| intersection | Data.Ring.Semi.BitSet | | | | | 1 (Function) | 2 (Function) | Data.Ring.Semi.BitSet | , complement
- , insert
- , delete
- , (\\)
-
- , fromList
- , fromDistinctAscList
-
- , toInteger
-
- , member
-
- , size
- , isComplemented
- ) where
-
-import Prelude hiding ( null, exponent, toInteger )
-import Data.Bits hiding ( complement )
-import qualified Data.Bits as Bits
-import Data.Data
-import Data.Ring.Semi.Natural
-import Data.Ring.Semi
-import Data.Monoid.Reducer
-import Data.Generator
-import Data.Ring.Algebra
-import Text.Read
-import Text.Show
-
-data BitSet a = BS
- { _countAtLeast :: !Int
-
- , _countAtMost :: !Int
+ , union
+ , intersection
+ , complement
+ , insert
+ , delete
+ , (\\)
+
+ , fromList
+ , fromDistinctAscList
+
+ , toInteger
+
+ , member
+
+ , size
+ , isComplemented
+ ) where
+
+import Prelude hiding ( null, exponent, toInteger )
+import Data.Bits hiding ( complement )
+import qualified Data.Bits as Bits
+import Data.Data
+import Data.Ring.Semi.Natural
+import Data.Ring.Semi
+import Data.Monoid.Reducer
+import Data.Generator
+import Data.Ring.Algebra
+import Text.Read
+import Text.Show
+
+data BitSet a = BS
+ { _countAtLeast :: !Int
hunk ./doc/html/monoids/src/Data-Ring-Semi-BitSet.html 70
- , _count :: Int
- , exponent :: !Int
- , _hwm :: !Int
- , mantissa :: !Integer
-
- , _universe :: (Int,Int)
- } deriving (Data, Typeable)
-
-
-bs :: Int -> Int -> Int -> Int -> Int -> Integer -> (Int,Int) -> BitSet a
-bs !a !b c !l !h !m u | a == b = BS a a a l h m u
- | otherwise = BS a b c l h m u
-
-
-
-toList :: Enum a => BitSet a -> [a]
-toList (BS _ _ _ l h m u)
- | m < 0 = map toEnum [ul..max (pred l) ul] ++ toList' l (map toEnum [min (succ h) uh..uh])
- | otherwise = toList' 0 []
- where
- ~(ul,uh) = u
- toList' :: Enum a => Int -> [a] -> [a]
- toList' !n t | n > h = t
- | testBit m (n l) = toEnum n : toList' (n+1) t
- | otherwise = toList' (n+1) t
-
-
-
-empty :: BitSet a
-empty = BS 0 0 0 0 0 0 undefined
-
-
-
-singleton :: Enum a => a -> BitSet a
-singleton x = BS 1 1 1 e e 1 undefined where e = fromEnum x
-
-
-
-
-null :: BitSet a -> Bool
-null (BS a b c _ _ _ _)
- | a > 0 = False
- | b == 0 = True
- | otherwise = c == 0
-
-
-
-size :: BitSet a -> Int
-size (BS a b c _ _ m (ul,uh))
- | a == b, m >= 0 = a
- | a == b = uh ul a
- | m >= 0 = c
- | otherwise = uh ul c
-
-
-
-full :: (Enum a, Bounded a) => BitSet a
-full = complement empty
-
-
-
-complement :: (Enum a, Bounded a) => BitSet a -> BitSet a
-complement r@(BS a b c l h m _) = BS (Bits.complement b) (Bits.complement a) (Bits.complement c) l h (Bits.complement m) u where
- u = (fromEnum (minBound `asArgTypeOf` r), fromEnum (maxBound `asArgTypeOf` r))
-
-
-
-recomplement :: BitSet a -> BitSet a
-recomplement (BS a b c l h m u) = BS (Bits.complement b) (Bits.complement a) (Bits.complement c) l h (Bits.complement m) u
-
-
-
-pseudoComplement :: BitSet a -> (Int,Int) -> BitSet a
-pseudoComplement (BS a b c l h m _) u = BS (Bits.complement b) (Bits.complement a) (Bits.complement c) l h (Bits.complement m) u
-
-
-
-fromList :: Enum a => [a] -> BitSet a
-fromList = foldr insert empty
-
-
-
-fromDistinctAscList :: Enum a => [a] -> BitSet a
-fromDistinctAscList [] = empty
-fromDistinctAscList (c:cs) = fromDistinctAscList' cs 1 0 1
- where
- l = fromEnum c
- fromDistinctAscList' :: Enum a => [a] -> Int -> Int -> Integer -> BitSet a
- fromDistinctAscList' [] !n !h !m = BS n n n l h m undefined
- fromDistinctAscList' (c':cs') !n _ !m = fromDistinctAscList' cs' (n+1) h' (setBit m (h' l))
- where
- h' = fromEnum c'
-
-
-
-insert :: Enum a => a -> BitSet a -> BitSet a
-insert x r@(BS a b c l h m u)
- | m < 0, e < l = r
- | m < 0, e > h = r
- | e < l = bs (a+1) (b+1) (c+1) e h (shiftL m (l e) .|. 1) u
- | e > h = bs (a+1) (b+1) (c+1) l p (setBit m p) u
- | testBit m p = r
- | otherwise = bs (a+1) (b+1) (c+1) l h (setBit m p) u
- where
- e = fromEnum x
- p = e l
-
-
-
-delete :: Enum a => a -> BitSet a -> BitSet a
-delete x r@(BS a b c l h m u)
- | m < 0, e < l = bs (a+1) (b+1) (c+1) e h (shiftL m (l e) .&. Bits.complement 1) u
- | m < 0, e > h = bs (a+1) (b+1) (c+1) l p (clearBit m p) u
- | e < l = r
- | e > h = r
- | testBit m p = bs (a1) (b1) (c1) l h (clearBit m p) u
- | otherwise = r
- where
- e = fromEnum x
- p = e l
-
-
-
-member :: Enum a => a -> BitSet a -> Bool
-member x (BS _ _ _ l h m _)
- | e < l = m < 0
- | e > h = m > 0
- | otherwise = testBit m (e l)
- where
- e = fromEnum x
-
-
-
-toInteger :: BitSet a -> Integer
-toInteger x = mantissa x `shift` exponent x
-
-
-union :: BitSet a -> BitSet a -> BitSet a
-union x@(BS a b c l h m u) y@(BS a' b' c' l' h' m' u')
- | l' < l = union y x
- | b == 0 = y
- | b' == 0 = x
- | a == 1 = entire u
- | a' == 1 = entire u'
- | m < 0, m' < 0 = recomplement (intersection (recomplement x) (recomplement y))
- | m' < 0 = recomplement (pseudoDiff (recomplement y) x u')
- | m < 0 = recomplement (pseudoDiff (recomplement x) y u)
- | h < l' = bs (a + a') (b + b') (c + c') l h' m'' u
- | otherwise = bs (a `max` a') (b + b') (recount m'') l (h `max` h') m'' u
- where
- m'' = m .|. shiftL m' (l' l)
- entire = BS (1) (1) (1) 0 0 (1)
-
-
-isComplemented :: BitSet a -> Bool
-isComplemented = (<0) . mantissa
-
-
-intersection :: BitSet a -> BitSet a -> BitSet a
-intersection x@(BS a b _ l h m u) y@(BS a' b' _ l' h' m' u')
- | l' < l = intersection y x
- | b == 0 = empty
- | b' == 0 = empty
- | a == 1 = y
- | a' == 1 = x
- | m < 0, m' < 0 = recomplement (union (recomplement x) (recomplement y))
- | m' < 0 = pseudoDiff x (recomplement y) u'
- | m < 0 = pseudoDiff y (recomplement x) u
- | h < l' = empty
- | otherwise = bs 0 (b `min` b') (recount m'') l'' (h `min` h') m'' u
- where
- l'' = max l l'
- m'' = shift m (l'' l) .&. shift m' (l'' l')
-
-
-
-
-pseudoDiff :: BitSet a -> BitSet a -> (Int,Int) -> BitSet a
-pseudoDiff x@(BS a _ _ l h m _) (BS _ b' _ l' h' m' _) u''
- | h < l' = x
- | h' < l = x
- | otherwise = bs (max (a b') 0) a (recount m'') l h m'' u''
- where
- m'' = m .&. shift (Bits.complement m') (l' l)
-
-
-difference :: Enum a => BitSet a -> BitSet a -> BitSet a
-difference x@(BS a b _ _ _ m u) y@(BS a' b' _ _ _ m' _)
- | a == 1 = pseudoComplement y u
- | a' == 1 = empty
- | b == 0 = empty
- | b' == 0 = x
- | m < 0, m' < 0 = pseudoDiff (recomplement y) (recomplement x) u
- | m < 0 = pseudoComplement (recomplement x `union` y) u
- | m' < 0 = x `union` recomplement y
- | otherwise = pseudoDiff x y u
-
-
-(\\) :: Enum a => BitSet a -> BitSet a -> BitSet a
-(\\) = difference
-
-instance Eq (BitSet a) where
- x@(BS _ _ _ l _ m u) == y@(BS _ _ _ l' _ m' _)
- | signum m == signum m' = shift m (l l'') == shift m' (l l'')
- | m' < 0 = y == x
- | otherwise = mask .&. shift m (l ul) == shift m' (l ul)
- where
- l'' = min l l'
- mask = setBit 0 (uh ul + 1) 1
- ul = fst u
- uh = snd u
-
-
-instance Ord (BitSet a) where
- BS _ _ _ l _ m _ `compare` BS _ _ _ l' _ m' _ = shift m (l'' l) `compare` shift m' (l'' l) where l'' = min l l'
-
-instance (Enum a, Bounded a) => Bounded (BitSet a) where
- minBound = empty
- maxBound = result where
- result = BS n n n l h m (l,h)
- n = h l + 1
- l = fromEnum (minBound `asArgTypeOf` result)
- h = fromEnum (maxBound `asArgTypeOf` result)
- m = setBit 0 n 1
-
-
-asArgTypeOf :: a -> f a -> a
-asArgTypeOf = const
-
-
-
-recount :: Integer -> Int
-recount !n
- | n < 0 = Bits.complement (recount (Bits.complement n))
- | otherwise = recount' 0 0
- where
- h = hwm n
- recount' !i !c
- | i > h = c
- | otherwise = recount' (i+1) (if testBit n i then c+1 else c)
-
-
-hwm :: Integer -> Int
-hwm !n
- | n < 0 = hwm (n)
- | n > 1 = scan p (2*p)
- | otherwise = 0
- where
- p = probe 1
-
- probe :: Int -> Int
- probe !i
- | bit (2*i) > n = i
- | otherwise = probe (2*i)
-
-
- scan :: Int -> Int -> Int
- scan !l !h
- | l == h = l
- | bit (m+1) > n = scan l m
- | otherwise = scan (m+1) h
- where m = l + (h l) `div` 2
-
-instance (Enum a, Show a) => Show (BitSet a) where
- showsPrec d x@(BS _ _ _ _ _ m u)
- | m < 0 = showParen (d > 10) $ showString "pseudoComplement " . showsPrec 11 (recomplement x) . showString " " . showsPrec 11 u
- | otherwise = showParen (d > 10) $ showString "fromDistinctAscList " . showsPrec 11 (toList x)
-
-instance (Enum a, Read a) => Read (BitSet a) where
- readPrec = parens $ complemented +++ normal where
- complemented = prec 10 $ do
- Ident "pseudoComplement" <- lexP
- x <- step readPrec
- pseudoComplement x `fmap` step readPrec
- normal = prec 10 $ do
- Ident "fromDistinctAscList" <- lexP
- fromDistinctAscList `fmap` step readPrec
-
-
-instance (Enum a, Bounded a) => Enum (BitSet a) where
- fromEnum b@(BS _ _ _ l _ m _) = fromInteger (shiftL m (l l'))
- where
- l' = fromEnum (minBound `asArgTypeOf` b)
- toEnum i = result
- where
- result = BS a i (recount m) l h m undefined
- l = fromEnum (minBound `asArgTypeOf` result)
- h = fromEnum (maxBound `asArgTypeOf` result)
- m = fromIntegral i
- a | m /= 0 = 1
- | otherwise = 0
-
-instance Enum a => Monoid (BitSet a) where
- mempty = empty
- mappend = union
-
-instance Enum a => Reducer a (BitSet a) where
- unit = singleton
- snoc = flip insert
- cons = insert
-
-instance (Bounded a, Enum a) => Multiplicative (BitSet a) where
- one = full
- times = intersection
-
-instance (Bounded a, Enum a) => LeftSemiNearRing (BitSet a)
-instance (Bounded a, Enum a) => RightSemiNearRing (BitSet a)
-instance (Bounded a, Enum a) => SemiRing (BitSet a)
-
-
-instance Enum a => LeftModule Natural (BitSet a) where
- 0 *. _ = empty
- _ *. m = m
-instance Enum a => RightModule Natural (BitSet a) where
- _ .* 0 = empty
- m .* _ = m
-instance Enum a => Module Natural (BitSet a)
-
-instance (Bounded a, Enum a) => LeftModule (BitSet a) (BitSet a) where (*.) = times
-instance (Bounded a, Enum a) => RightModule (BitSet a) (BitSet a) where (.*) = times
-instance (Bounded a, Enum a) => Module (BitSet a) (BitSet a)
-
-instance (Bounded a, Enum a) => Algebra Natural (BitSet a)
-
-instance Enum a => Generator (BitSet a) where
- type Elem (BitSet a) = a
- mapReduce f = mapReduce f . toList
+ , _countAtMost :: !Int
+
+ , _count :: Int
+ , exponent :: !Int
+ , _hwm :: !Int
+ , mantissa :: !Integer
+
+ , _universe :: (Int,Int)
+ } deriving (Data, Typeable)
+
+
+bs :: Int -> Int -> Int -> Int -> Int -> Integer -> (Int,Int) -> BitSet a
+bs !a !b c !l !h !m u | a == b = BS a a a l h m u
+ | otherwise = BS a b c l h m u
+
+
+
+toList :: Enum a => BitSet a -> [a]
+toList (BS _ _ _ l h m u)
+ | m < 0 = map toEnum [ul..max (pred l) ul] ++ toList' l (map toEnum [min (succ h) uh..uh])
+ | otherwise = toList' 0 []
+ where
+ ~(ul,uh) = u
+ toList' :: Enum a => Int -> [a] -> [a]
+ toList' !n t | n > h = t
+ | testBit m (n l) = toEnum n : toList' (n+1) t
+ | otherwise = toList' (n+1) t
+
+
+
+empty :: BitSet a
+empty = BS 0 0 0 0 0 0 undefined
+
+
+
+singleton :: Enum a => a -> BitSet a
+singleton x = BS 1 1 1 e e 1 undefined where e = fromEnum x
+
+
+
+
+null :: BitSet a -> Bool
+null (BS a b c _ _ _ _)
+ | a > 0 = False
+ | b == 0 = True
+ | otherwise = c == 0
+
+
+
+size :: BitSet a -> Int
+size (BS a b c _ _ m (ul,uh))
+ | a == b, m >= 0 = a
+ | a == b = uh ul a
+ | m >= 0 = c
+ | otherwise = uh ul c
+
+
+
+full :: (Enum a, Bounded a) => BitSet a
+full = complement empty
+
+
+
+complement :: (Enum a, Bounded a) => BitSet a -> BitSet a
+complement r@(BS a b c l h m _) = BS (Bits.complement b) (Bits.complement a) (Bits.complement c) l h (Bits.complement m) u where
+ u = (fromEnum (minBound `asArgTypeOf` r), fromEnum (maxBound `asArgTypeOf` r))
+
+
+
+recomplement :: BitSet a -> BitSet a
+recomplement (BS a b c l h m u) = BS (Bits.complement b) (Bits.complement a) (Bits.complement c) l h (Bits.complement m) u
+
+
+
+pseudoComplement :: BitSet a -> (Int,Int) -> BitSet a
+pseudoComplement (BS a b c l h m _) u = BS (Bits.complement b) (Bits.complement a) (Bits.complement c) l h (Bits.complement m) u
+
+
+
+fromList :: Enum a => [a] -> BitSet a
+fromList = foldr insert empty
+
+
+
+fromDistinctAscList :: Enum a => [a] -> BitSet a
+fromDistinctAscList [] = empty
+fromDistinctAscList (c:cs) = fromDistinctAscList' cs 1 0 1
+ where
+ l = fromEnum c
+ fromDistinctAscList' :: Enum a => [a] -> Int -> Int -> Integer -> BitSet a
+ fromDistinctAscList' [] !n !h !m = BS n n n l h m undefined
+ fromDistinctAscList' (c':cs') !n _ !m = fromDistinctAscList' cs' (n+1) h' (setBit m (h' l))
+ where
+ h' = fromEnum c'
+
+
+
+insert :: Enum a => a -> BitSet a -> BitSet a
+insert x r@(BS a b c l h m u)
+ | m < 0, e < l = r
+ | m < 0, e > h = r
+ | e < l = bs (a+1) (b+1) (c+1) e h (shiftL m (l e) .|. 1) u
+ | e > h = bs (a+1) (b+1) (c+1) l p (setBit m p) u
+ | testBit m p = r
+ | otherwise = bs (a+1) (b+1) (c+1) l h (setBit m p) u
+ where
+ e = fromEnum x
+ p = e l
+
+
+
+delete :: Enum a => a -> BitSet a -> BitSet a
+delete x r@(BS a b c l h m u)
+ | m < 0, e < l = bs (a+1) (b+1) (c+1) e h (shiftL m (l e) .&. Bits.complement 1) u
+ | m < 0, e > h = bs (a+1) (b+1) (c+1) l p (clearBit m p) u
+ | e < l = r
+ | e > h = r
+ | testBit m p = bs (a1) (b1) (c1) l h (clearBit m p) u
+ | otherwise = r
+ where
+ e = fromEnum x
+ p = e l
+
+
+
+member :: Enum a => a -> BitSet a -> Bool
+member x (BS _ _ _ l h m _)
+ | e < l = m < 0
+ | e > h = m > 0
+ | otherwise = testBit m (e l)
+ where
+ e = fromEnum x
+
+
+
+toInteger :: BitSet a -> Integer
+toInteger x = mantissa x `shift` exponent x
+
+
+union :: BitSet a -> BitSet a -> BitSet a
+union x@(BS a b c l h m u) y@(BS a' b' c' l' h' m' u')
+ | l' < l = union y x
+ | b == 0 = y
+ | b' == 0 = x
+ | a == 1 = entire u
+ | a' == 1 = entire u'
+ | m < 0, m' < 0 = recomplement (intersection (recomplement x) (recomplement y))
+ | m' < 0 = recomplement (pseudoDiff (recomplement y) x u')
+ | m < 0 = recomplement (pseudoDiff (recomplement x) y u)
+ | h < l' = bs (a + a') (b + b') (c + c') l h' m'' u
+ | otherwise = bs (a `max` a') (b + b') (recount m'') l (h `max` h') m'' u
+ where
+ m'' = m .|. shiftL m' (l' l)
+ entire = BS (1) (1) (1) 0 0 (1)
+
+
+isComplemented :: BitSet a -> Bool
+isComplemented = (<0) . mantissa
+
+
+intersection :: BitSet a -> BitSet a -> BitSet a
+intersection x@(BS a b _ l h m u) y@(BS a' b' _ l' h' m' u')
+ | l' < l = intersection y x
+ | b == 0 = empty
+ | b' == 0 = empty
+ | a == 1 = y
+ | a' == 1 = x
+ | m < 0, m' < 0 = recomplement (union (recomplement x) (recomplement y))
+ | m' < 0 = pseudoDiff x (recomplement y) u'
+ | m < 0 = pseudoDiff y (recomplement x) u
+ | h < l' = empty
+ | otherwise = bs 0 (b `min` b') (recount m'') l'' (h `min` h') m'' u
+ where
+ l'' = max l l'
+ m'' = shift m (l'' l) .&. shift m' (l'' l')
+
+
+
+
+pseudoDiff :: BitSet a -> BitSet a -> (Int,Int) -> BitSet a
+pseudoDiff x@(BS a _ _ l h m _) (BS _ b' _ l' h' m' _) u''
+ | h < l' = x
+ | h' < l = x
+ | otherwise = bs (max (a b') 0) a (recount m'') l h m'' u''
+ where
+ m'' = m .&. shift (Bits.complement m') (l' l)
+
+
+difference :: Enum a => BitSet a -> BitSet a -> BitSet a
+difference x@(BS a b _ _ _ m u) y@(BS a' b' _ _ _ m' _)
+ | a == 1 = pseudoComplement y u
+ | a' == 1 = empty
+ | b == 0 = empty
+ | b' == 0 = x
+ | m < 0, m' < 0 = pseudoDiff (recomplement y) (recomplement x) u
+ | m < 0 = pseudoComplement (recomplement x `union` y) u
+ | m' < 0 = x `union` recomplement y
+ | otherwise = pseudoDiff x y u
+
+
+(\\) :: Enum a => BitSet a -> BitSet a -> BitSet a
+(\\) = difference
+
+instance Eq (BitSet a) where
+ x@(BS _ _ _ l _ m u) == y@(BS _ _ _ l' _ m' _)
+ | signum m == signum m' = shift m (l l'') == shift m' (l l'')
+ | m' < 0 = y == x
+ | otherwise = mask .&. shift m (l ul) == shift m' (l ul)
+ where
+ l'' = min l l'
+ mask = setBit 0 (uh ul + 1) 1
+ ul = fst u
+ uh = snd u
+
+
+
+
+instance (Enum a, Bounded a) => Bounded (BitSet a) where
+ minBound = empty
+ maxBound = result where
+ result = BS n n n l h m (l,h)
+ n = h l + 1
+ l = fromEnum (minBound `asArgTypeOf` result)
+ h = fromEnum (maxBound `asArgTypeOf` result)
+ m = setBit 0 n 1
+
+
+asArgTypeOf :: a -> f a -> a
+asArgTypeOf = const
+
+
+
+recount :: Integer -> Int
+recount !n
+ | n < 0 = Bits.complement (recount (Bits.complement n))
+ | otherwise = recount' 0 0
+ where
+ h = hwm n
+ recount' !i !c
+ | i > h = c
+ | otherwise = recount' (i+1) (if testBit n i then c+1 else c)
+
+
+hwm :: Integer -> Int
+hwm !n
+ | n < 0 = hwm (n)
+ | n > 1 = scan p (2*p)
+ | otherwise = 0
+ where
+ p = probe 1
+
+ probe :: Int -> Int
+ probe !i
+ | bit (2*i) > n = i
+ | otherwise = probe (2*i)
+
+
+ scan :: Int -> Int -> Int
+ scan !l !h
+ | l == h = l
+ | bit (m+1) > n = scan l m
+ | otherwise = scan (m+1) h
+ where m = l + (h l) `div` 2
+
+instance (Enum a, Show a) => Show (BitSet a) where
+ showsPrec d x@(BS _ _ _ _ _ m u)
+ | m < 0 = showParen (d > 10) $ showString "pseudoComplement " . showsPrec 11 (recomplement x) . showString " " . showsPrec 11 u
+ | otherwise = showParen (d > 10) $ showString "fromDistinctAscList " . showsPrec 11 (toList x)
+
+instance (Enum a, Read a) => Read (BitSet a) where
+ readPrec = parens $ complemented +++ normal where
+ complemented = prec 10 $ do
+ Ident "pseudoComplement" <- lexP
+ x <- step readPrec
+ pseudoComplement x `fmap` step readPrec
+ normal = prec 10 $ do
+ Ident "fromDistinctAscList" <- lexP
+ fromDistinctAscList `fmap` step readPrec
+
+
+instance (Enum a, Bounded a) => Enum (BitSet a) where
+ fromEnum b@(BS _ _ _ l _ m _) = fromInteger (shiftL m (l l'))
+ where
+ l' = fromEnum (minBound `asArgTypeOf` b)
+ toEnum i = result
+ where
+ result = BS a i (recount m) l h m undefined
+ l = fromEnum (minBound `asArgTypeOf` result)
+ h = fromEnum (maxBound `asArgTypeOf` result)
+ m = fromIntegral i
+ a | m /= 0 = 1
+ | otherwise = 0
+
+instance Enum a => Monoid (BitSet a) where
+ mempty = empty
+ mappend = union
+
+instance Enum a => Reducer a (BitSet a) where
+ unit = singleton
+ snoc = flip insert
+ cons = insert
+
+instance (Bounded a, Enum a) => Multiplicative (BitSet a) where
+ one = full
+ times = intersection
+
+instance (Bounded a, Enum a) => LeftSemiNearRing (BitSet a)
+instance (Bounded a, Enum a) => RightSemiNearRing (BitSet a)
+instance (Bounded a, Enum a) => SemiRing (BitSet a)
+
+
+instance Enum a => LeftModule Natural (BitSet a) where
+ 0 *. _ = empty
+ _ *. m = m
+instance Enum a => RightModule Natural (BitSet a) where
+ _ .* 0 = empty
+ m .* _ = m
+instance Enum a => Module Natural (BitSet a)
+
+instance (Bounded a, Enum a) => LeftModule (BitSet a) (BitSet a) where (*.) = times
+instance (Bounded a, Enum a) => RightModule (BitSet a) (BitSet a) where (.*) = times
+instance (Bounded a, Enum a) => Module (BitSet a) (BitSet a)
+
+instance (Bounded a, Enum a) => Algebra Natural (BitSet a)
+
+instance Enum a => Generator (BitSet a) where
+ type Elem (BitSet a) = a
+ mapReduce f = mapReduce f . toList
}
|