Something went wrong. Try again.
dependent-types proof-assistant
Something went wrong. Try again.
2.0 kB · 69 lines
Haskell
at main
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970
{-|Small sets represented as a 'Word64'.For an element type, you have to make sure that the Enum instance maps values to the 0-63 range.-}
module Utils.SmallSet where
import Utils.Listimport Data.Word (Word64)import Data.Bits
type role SmallSet representationalnewtype SmallSet a = SmallSet Word64 deriving (Eq, Ord) via Word64
instance (Show a, Enum a) => Show (SmallSet a) where showsPrec p s = showParen (p > 10) $ ("SmallSet " ++) . showsPrec 11 (fold (flip (:)) [] s)
instance Semigroup (SmallSet a) where {-# inline (<>) #-} (<>) = \(SmallSet x) (SmallSet y) -> SmallSet (x .|. y)
instance Monoid (SmallSet a) where {-# inline mempty #-} mempty = SmallSet 0
{-# inlinable toList #-}toList :: Enum a => SmallSet a -> List atoList = fold (flip Cons) Nil
{-# inlinable fromList #-}fromList :: Enum a => [a] -> SmallSet afromList = foldl' (\s a -> insert a s) mempty
{-# inline fold #-}fold :: Enum a => (b -> a -> b) -> b -> SmallSet a -> bfold = \f b (SmallSet as) -> let go i b 0 = b go i b as = case countTrailingZeros as of shift -> go (i + shift + 1) (f b (toEnum (i + shift))) (unsafeShiftR as (shift + 1)) in go 0 b as
{-# inline null #-}null :: SmallSet a -> Boolnull = \s -> s == mempty
{-# inline insert #-}insert :: Enum a => a -> SmallSet a -> SmallSet ainsert = \a (SmallSet as) -> SmallSet (as .|. unsafeShiftL 1 (fromEnum a))
{-# inline member #-}member :: Enum a => a -> SmallSet a -> Boolmember = \a (SmallSet as) -> toEnum (fromIntegral (unsafeShiftR as (fromEnum a) .&. 1))
{-# inline delete #-}delete :: Enum a => a -> SmallSet a -> SmallSet adelete = \a (SmallSet as) -> SmallSet (as .&. complement (unsafeShiftL 1 (fromEnum a)))
{-# inline notMember #-}notMember :: Enum a => a -> SmallSet a -> BoolnotMember = \a s -> not (member a s)
{-# inline singleton #-}singleton :: Enum a => a -> SmallSet asingleton = \a -> SmallSet (unsafeShiftL 1 (fromEnum a))