ModuleAgda-2.7.0.1Haskell2010

Agda.Utils.SmallSet

Small sets represented as a bitmask for fast membership checking.

With the exception of converting to/from lists, all operations are O(1).

Mimics the interface of Data.Set.

Import as: import qualified Agda.Utils.SmallSet as SmallSet import Agda.Utils.SmallSet (SmallSet)

1 type
2 classes
19 values

PackageAgda-2.7.0.1
Exports22
LanguageHaskell2010
LicenceMIT
SourceSmallSet.hs

newtypenewtype SmallSet a

Constructors

SmallSet
- theSmallSet :: Word64

Instances11Collection, Singleton, Eq, Ord, Show, Semigroup, …

SmallSetElement a => Collection a (SmallSet a)Defined in Agda-2.7.0.1 · Agda.Utils.Singleton
SmallSetElement a => Singleton a (SmallSet a)Defined in Agda-2.7.0.1 · Agda.Utils.Singleton
Eq (SmallSet a)Defined in Agda-2.7.0.1 · Agda.Utils.SmallSet
Ord (SmallSet a)Defined in Agda-2.7.0.1 · Agda.Utils.SmallSet
Show (SmallSet a)Defined in Agda-2.7.0.1 · Agda.Utils.SmallSet
SmallSetElement a => Semigroup (SmallSet a)Defined in Agda-2.7.0.1 · Agda.Utils.SmallSet
SmallSetElement a => Monoid (SmallSet a)Defined in Agda-2.7.0.1 · Agda.Utils.SmallSet
NFData (SmallSet a)Defined in Agda-2.7.0.1 · Agda.Utils.SmallSet
SmallSetElement a => Null (SmallSet a)Defined in Agda-2.7.0.1 · Agda.Utils.SmallSet
KillRange (SmallSet FunctionFlag)Defined in Agda-2.7.0.1 · Agda.TypeChecking.Monad.Base
Typeable a => EmbPrj (SmallSet a)Defined in Agda-2.7.0.1 · Agda.TypeChecking.Serialise.Instances.Common · orphan

classclass (Bounded a, Ix a) => SmallSetElement a

An element in a small set.

This must implement Bounded and Ix, and contain at most 64 values.

Instances2SmallSetElement

SmallSetElement AllowedReductionDefined in Agda-2.7.0.1 · Agda.TypeChecking.Monad.Base
SmallSetElement FunctionFlagDefined in Agda-2.7.0.1 · Agda.TypeChecking.Monad.Base

classclass Ord a => Ix a where

The Ix class is used to map a contiguous subrange of values in a type onto integers. It is used primarily for array indexing (see the array package).

The first argument (l,u) of each of these operations is a pair specifying the lower and upper bounds of a contiguous subrange of values.

An implementation is entitled to assume the following laws about these operations:

inRange (l,u) i == elem i (range (l,u))
range (l,u) !! index (l,u) i == i, when inRange (l,u) i
map (index (l,u)) (range (l,u))) == [0..rangeSize (l,u)-1]
rangeSize (l,u) == length (range (l,u))

Instances105Ix, …

Ix AllowedReductionDefined in Agda-2.7.0.1 · Agda.TypeChecking.Monad.Base
Ix FunctionFlagDefined in Agda-2.7.0.1 · Agda.TypeChecking.Monad.Base
Ix BlinkSpeedDefined in ansi-terminal-types-1.1.3 · System.Console.ANSI.Types
Ix ColorDefined in ansi-terminal-types-1.1.3 · System.Console.ANSI.Types
Ix ColorIntensityDefined in ansi-terminal-types-1.1.3 · System.Console.ANSI.Types
Ix ConsoleIntensityDefined in ansi-terminal-types-1.1.3 · System.Console.ANSI.Types
Ix ConsoleLayerDefined in ansi-terminal-types-1.1.3 · System.Console.ANSI.Types
Ix UnderliningDefined in ansi-terminal-types-1.1.3 · System.Console.ANSI.Types
Ix IntegerDefined in ghc-internal-9.1003.0 · GHC.Internal.Ix
Ix NaturalDefined in ghc-internal-9.1003.0 · GHC.Internal.Ix
Ix VoidDefined in ghc-internal-9.1003.0 · GHC.Internal.Ix
Ix CBoolDefined in ghc-internal-9.1003.0 · GHC.Internal.Foreign.C.Types
Ix CCharDefined in ghc-internal-9.1003.0 · GHC.Internal.Foreign.C.Types
Ix CIntDefined in ghc-internal-9.1003.0 · GHC.Internal.Foreign.C.Types
Ix CIntMaxDefined in ghc-internal-9.1003.0 · GHC.Internal.Foreign.C.Types
Ix CIntPtrDefined in ghc-internal-9.1003.0 · GHC.Internal.Foreign.C.Types
Ix CLLongDefined in ghc-internal-9.1003.0 · GHC.Internal.Foreign.C.Types
Ix CLongDefined in ghc-internal-9.1003.0 · GHC.Internal.Foreign.C.Types
Ix CPtrdiffDefined in ghc-internal-9.1003.0 · GHC.Internal.Foreign.C.Types
Ix CSCharDefined in ghc-internal-9.1003.0 · GHC.Internal.Foreign.C.Types
Ix CShortDefined in ghc-internal-9.1003.0 · GHC.Internal.Foreign.C.Types
Ix CSigAtomicDefined in ghc-internal-9.1003.0 · GHC.Internal.Foreign.C.Types
Ix CSizeDefined in ghc-internal-9.1003.0 · GHC.Internal.Foreign.C.Types
Ix CUCharDefined in ghc-internal-9.1003.0 · GHC.Internal.Foreign.C.Types
Ix CUIntDefined in ghc-internal-9.1003.0 · GHC.Internal.Foreign.C.Types
Ix CUIntMaxDefined in ghc-internal-9.1003.0 · GHC.Internal.Foreign.C.Types
Ix CUIntPtrDefined in ghc-internal-9.1003.0 · GHC.Internal.Foreign.C.Types
Ix CULLongDefined in ghc-internal-9.1003.0 · GHC.Internal.Foreign.C.Types
Ix CULongDefined in ghc-internal-9.1003.0 · GHC.Internal.Foreign.C.Types
Ix CUShortDefined in ghc-internal-9.1003.0 · GHC.Internal.Foreign.C.Types
Ix CWcharDefined in ghc-internal-9.1003.0 · GHC.Internal.Foreign.C.Types
Ix IntPtrDefined in ghc-internal-9.1003.0 · GHC.Internal.Foreign.Ptr
Ix WordPtrDefined in ghc-internal-9.1003.0 · GHC.Internal.Foreign.Ptr
Ix AssociativityDefined in ghc-internal-9.1003.0 · GHC.Internal.Generics
Ix DecidedStrictnessDefined in ghc-internal-9.1003.0 · GHC.Internal.Generics
Ix SourceStrictnessDefined in ghc-internal-9.1003.0 · GHC.Internal.Generics
Ix SourceUnpackednessDefined in ghc-internal-9.1003.0 · GHC.Internal.Generics
Ix SeekModeDefined in ghc-internal-9.1003.0 · GHC.Internal.IO.Device
Ix IOModeDefined in ghc-internal-9.1003.0 · GHC.Internal.IO.IOMode
Ix Int16Defined in ghc-internal-9.1003.0 · GHC.Internal.Int
Ix Int32Defined in ghc-internal-9.1003.0 · GHC.Internal.Int
Ix Int64Defined in ghc-internal-9.1003.0 · GHC.Internal.Int
Ix Int8Defined in ghc-internal-9.1003.0 · GHC.Internal.Int
Ix CBlkCntDefined in ghc-internal-9.1003.0 · GHC.Internal.System.Posix.Types
Ix CBlkSizeDefined in ghc-internal-9.1003.0 · GHC.Internal.System.Posix.Types
Ix CClockIdDefined in ghc-internal-9.1003.0 · GHC.Internal.System.Posix.Types
Ix CDevDefined in ghc-internal-9.1003.0 · GHC.Internal.System.Posix.Types
Ix CFsBlkCntDefined in ghc-internal-9.1003.0 · GHC.Internal.System.Posix.Types
Ix CFsFilCntDefined in ghc-internal-9.1003.0 · GHC.Internal.System.Posix.Types
Ix CGidDefined in ghc-internal-9.1003.0 · GHC.Internal.System.Posix.Types
Ix CIdDefined in ghc-internal-9.1003.0 · GHC.Internal.System.Posix.Types
Ix CInoDefined in ghc-internal-9.1003.0 · GHC.Internal.System.Posix.Types
Ix CKeyDefined in ghc-internal-9.1003.0 · GHC.Internal.System.Posix.Types
Ix CModeDefined in ghc-internal-9.1003.0 · GHC.Internal.System.Posix.Types
Ix CNfdsDefined in ghc-internal-9.1003.0 · GHC.Internal.System.Posix.Types
Ix CNlinkDefined in ghc-internal-9.1003.0 · GHC.Internal.System.Posix.Types
Ix COffDefined in ghc-internal-9.1003.0 · GHC.Internal.System.Posix.Types
Ix CPidDefined in ghc-internal-9.1003.0 · GHC.Internal.System.Posix.Types
Ix CRLimDefined in ghc-internal-9.1003.0 · GHC.Internal.System.Posix.Types
Ix CSocklenDefined in ghc-internal-9.1003.0 · GHC.Internal.System.Posix.Types
Ix CSsizeDefined in ghc-internal-9.1003.0 · GHC.Internal.System.Posix.Types
Ix CTcflagDefined in ghc-internal-9.1003.0 · GHC.Internal.System.Posix.Types
Ix CUidDefined in ghc-internal-9.1003.0 · GHC.Internal.System.Posix.Types
Ix FdDefined in ghc-internal-9.1003.0 · GHC.Internal.System.Posix.Types
Ix GeneralCategoryDefined in ghc-internal-9.1003.0 · GHC.Internal.Unicode
Ix Word16Defined in ghc-internal-9.1003.0 · GHC.Internal.Word
Ix Word32Defined in ghc-internal-9.1003.0 · GHC.Internal.Word
Ix Word64Defined in ghc-internal-9.1003.0 · GHC.Internal.Word
Ix Word8Defined in ghc-internal-9.1003.0 · GHC.Internal.Word
Ix BoolDefined in ghc-internal-9.1003.0 · GHC.Internal.Ix
Ix CharDefined in ghc-internal-9.1003.0 · GHC.Internal.Ix
Ix IntDefined in ghc-internal-9.1003.0 · GHC.Internal.Ix
Ix OrderingDefined in ghc-internal-9.1003.0 · GHC.Internal.Ix
Ix WordDefined in ghc-internal-9.1003.0 · GHC.Internal.Ix
Ix PeanoDefined in peano-0.1.0.2 · Data.Peano
Ix DayDefined in time-1.12.2 · Data.Time.Calendar.Days
Ix MonthDefined in time-1.12.2 · Data.Time.Calendar.Month
Ix QuarterDefined in time-1.12.2 · Data.Time.Calendar.Quarter
Ix QuarterOfYearDefined in time-1.12.2 · Data.Time.Calendar.Quarter
Ix DayOfWeekDefined in time-1.12.2 · Data.Time.Calendar.Week
Ix ()Defined in ghc-internal-9.1003.0 · GHC.Internal.Ix
Ix a => Ix (Large a)Defined in QuickCheck-2.15.0.1 · Test.QuickCheck.Modifiers
Ix a => Ix (Small a)Defined in QuickCheck-2.15.0.1 · Test.QuickCheck.Modifiers
Ix a => Ix (Identity a)Defined in ghc-internal-9.1003.0 · GHC.Internal.Data.Functor.Identity
Ix a => Ix (Down a)Defined in ghc-internal-9.1003.0 · GHC.Internal.Data.Ord
Ix a => Ix (a)Defined in ghc-internal-9.1003.0 · GHC.Internal.Ix
Ix i => Ix (MIx i)Defined in Agda-2.7.0.1 · Agda.Termination.SparseMatrix
Ix (Proxy s)Defined in ghc-internal-9.1003.0 · GHC.Internal.Data.Proxy
(Ix a, Ix b) => Ix (Pair a b)Defined in strict-0.5.1 · Data.Strict.Tuple
(Ix a, Ix b) => Ix (a, b)Defined in ghc-internal-9.1003.0 · GHC.Internal.Ix
Ix a => Ix (Const a b)Defined in ghc-internal-9.1003.0 · GHC.Internal.Data.Functor.Const
Ix b => Ix (Tagged s b)Defined in tagged-0.8.9 · Data.Tagged
(Ix a1, Ix a2, Ix a3) => Ix (a1, a2, a3)Defined in ghc-internal-9.1003.0 · GHC.Internal.Ix
(Ix a1, Ix a2, Ix a3, Ix a4) => Ix (a1, a2, a3, a4)Defined in ghc-internal-9.1003.0 · GHC.Internal.Ix
(Ix a1, Ix a2, Ix a3, Ix a4, Ix a5) => Ix (a1, a2, a3, a4, a5)Defined in ghc-internal-9.1003.0 · GHC.Internal.Ix
(Ix a1, Ix a2, Ix a3, Ix a4, Ix a5, Ix a6) => Ix (a1, a2, a3, a4, a5, a6)Defined in ghc-internal-9.1003.0 · GHC.Internal.Ix
(Ix a1, Ix a2, Ix a3, Ix a4, Ix a5, Ix a6, Ix a7) => Ix (a1, a2, a3, a4, a5, a6, a7)Defined in ghc-internal-9.1003.0 · GHC.Internal.Ix
(Ix a1, Ix a2, Ix a3, Ix a4, Ix a5, Ix a6, Ix a7, Ix a8) => Ix (a1, a2, a3, a4, a5, a6, a7, a8)Defined in ghc-internal-9.1003.0 · GHC.Internal.Ix
(Ix a1, Ix a2, Ix a3, Ix a4, Ix a5, Ix a6, Ix a7, Ix a8, Ix a9) => Ix (a1, a2, a3, a4, a5, a6, a7, a8, a9)Defined in ghc-internal-9.1003.0 · GHC.Internal.Ix
(Ix a1, Ix a2, Ix a3, Ix a4, Ix a5, Ix a6, Ix a7, Ix a8, Ix a9, Ix aA) => Ix (a1, a2, a3, a4, a5, a6, a7, a8, a9, aA)Defined in ghc-internal-9.1003.0 · GHC.Internal.Ix
(Ix a1, Ix a2, Ix a3, Ix a4, Ix a5, Ix a6, Ix a7, Ix a8, Ix a9, Ix aA, Ix aB) => Ix (a1, a2, a3, a4, a5, a6, a7, a8, a9, aA, aB)Defined in ghc-internal-9.1003.0 · GHC.Internal.Ix
(Ix a1, Ix a2, Ix a3, Ix a4, Ix a5, Ix a6, Ix a7, Ix a8, Ix a9, Ix aA, Ix aB, Ix aC) => Ix (a1, a2, a3, a4, a5, a6, a7, a8, a9, aA, aB, aC)Defined in ghc-internal-9.1003.0 · GHC.Internal.Ix
(Ix a1, Ix a2, Ix a3, Ix a4, Ix a5, Ix a6, Ix a7, Ix a8, Ix a9, Ix aA, Ix aB, Ix aC, Ix aD) => Ix (a1, a2, a3, a4, a5, a6, a7, a8, a9, aA, aB, aC, aD)Defined in ghc-internal-9.1003.0 · GHC.Internal.Ix
(Ix a1, Ix a2, Ix a3, Ix a4, Ix a5, Ix a6, Ix a7, Ix a8, Ix a9, Ix aA, Ix aB, Ix aC, Ix aD, Ix aE) => Ix (a1, a2, a3, a4, a5, a6, a7, a8, a9, aA, aB, aC, aD, aE)Defined in ghc-internal-9.1003.0 · GHC.Internal.Ix
(Ix a1, Ix a2, Ix a3, Ix a4, Ix a5, Ix a6, Ix a7, Ix a8, Ix a9, Ix aA, Ix aB, Ix aC, Ix aD, Ix aE, Ix aF) => Ix (a1, a2, a3, a4, a5, a6, a7, a8, a9, aA, aB, aC, aD, aE, aF)Defined in ghc-internal-9.1003.0 · GHC.Internal.Ix

value(\\) :: SmallSetElement a => SmallSet a -> SmallSet a -> SmallSet a

Time O(1).

valuecomplement :: SmallSetElement a => SmallSet a -> SmallSet a

Time O(n).

valuedelete :: SmallSetElement a => a -> SmallSet a -> SmallSet a

Time O(1).

valuedifference :: SmallSetElement a => SmallSet a -> SmallSet a -> SmallSet a

Time O(1).

valueelems :: SmallSetElement a => SmallSet a -> [a]

Time O(n).

valueempty :: SmallSetElement a => SmallSet a

The empty set. Time O(1).

valuefromList :: SmallSetElement a => [a] -> SmallSet a

Time O(n).

valuefromAscList :: SmallSetElement a => [a] -> SmallSet a

Time O(n).

valuefromDistinctAscList :: SmallSetElement a => [a] -> SmallSet a

Time O(n).

valueinsert :: SmallSetElement a => a -> SmallSet a -> SmallSet a

Time O(1).

valueintersection :: SmallSetElement a => SmallSet a -> SmallSet a -> SmallSet a

Time O(1).

valuemember :: SmallSetElement a => a -> SmallSet a -> Bool

Time O(1).

valuenotMember :: SmallSetElement a => a -> SmallSet a -> Bool

not . member a. Time O(1).

valuenull :: SmallSetElement a => SmallSet a -> Bool

Time O(1).

valuesingleton :: SmallSetElement a => a -> SmallSet a

A singleton set. Time O(1).

valuetoList :: SmallSetElement a => SmallSet a -> [a]

Time O(n).

valuetoAscList :: SmallSetElement a => SmallSet a -> [a]

Time O(n).

valuetotal :: SmallSetElement a => SmallSet a

The full set. Time O(1).

valueunion :: SmallSetElement a => SmallSet a -> SmallSet a -> SmallSet a

Time O(n).