universe-base-1.1: A class for finite and recursively enumerable types.

Safe HaskellSafe
LanguageHaskell2010

Data.Universe.Helpers

Contents

Synopsis

Documentation

This module is for functions that are useful for writing instances, but not necessarily for using them (and hence are not exported by the main module to avoid cluttering up the namespace).

Building lists

universeDef :: (Bounded a, Enum a) => [a] Source #

For many types, the universe should be [minBound .. maxBound]; universeDef makes it easy to make such types an instance of Universe via the snippet

instance Universe Foo where universe = universeDef

interleave :: [[a]] -> [a] Source #

Fair n-way interleaving: given a finite number of (possibly infinite) lists, produce a single list such that whenever v has finite index in one of the input lists, v also has finite index in the output list. No list's elements occur more frequently (on average) than another's.

diagonal :: [[a]] -> [a] Source #

Unfair n-way interleaving: given a possibly infinite number of (possibly infinite) lists, produce a single list such that whenever v has finite index in an input list at finite index, v also has finite index in the output list. Elements from lists at lower index occur more frequently, but not exponentially so.

diagonals :: [[a]] -> [[a]] Source #

Like diagonal, but expose a tiny bit more (non-semantic) information: if you lay out the input list in two dimensions, each list in the result will be one of the diagonals of the input. In particular, each element of the output will be a list whose elements are each from a distinct input list.

(+++) :: [a] -> [a] -> [a] Source #

Fair 2-way interleaving.

cartesianProduct :: (a -> b -> c) -> [a] -> [b] -> [c] Source #

Slightly unfair 2-way Cartesian product: given two (possibly infinite) lists, produce a single list such that whenever v and w have finite indices in the input lists, (v,w) has finite index in the output list. Lower indices occur as the fst part of the tuple more frequently, but not exponentially so.

(+*+) :: [a] -> [b] -> [(a, b)] Source #

(<+*+>) :: [a -> b] -> [a] -> [b] Source #

A +*+ with application.

cartesianProduct ($)

choices :: [[a]] -> [[a]] Source #

Slightly unfair n-way Cartesian product: given a finite number of (possibly infinite) lists, produce a single list such that whenever vi has finite index in list i for each i, [v1, ..., vn] has finite index in the output list.

Building cardinalities

These functions are handy for inheriting the definition of cardinality in a newtype instance. For example, one might write

newtype Foo = Foo Bar
instance Finite Foo where cardinality = retagWith Foo cardinality

retagWith :: (a -> b) -> Tagged a x -> Tagged b x Source #

retag :: Tagged s b -> Tagged t b #

Some times you need to change the tag you have lying around. Idiomatic usage is to make a new combinator for the relationship between the tags that you want to enforce, and define that combinator using retag.

data Succ n
retagSucc :: Tagged n a -> Tagged (Succ n) a
retagSucc = retag

newtype Tagged (s :: k) b :: forall k. k -> Type -> Type #

A Tagged s b value is a value b with an attached phantom type s. This can be used in place of the more traditional but less safe idiom of passing in an undefined value with the type, because unlike an (s -> b), a Tagged s b can't try to use the argument s as a real value.

Moreover, you don't have to rely on the compiler to inline away the extra argument, because the newtype is "free"

Tagged has kind k -> * -> * if the compiler supports PolyKinds, therefore there is an extra k showing in the instance haddocks that may cause confusion.

Constructors

Tagged 

Fields

Instances
Bitraversable (Tagged :: Type -> Type -> Type) 
Instance details

Defined in Data.Tagged

Methods

bitraverse :: Applicative f => (a -> f c) -> (b -> f d) -> Tagged a b -> f (Tagged c d) #

Bifoldable (Tagged :: Type -> Type -> Type) 
Instance details

Defined in Data.Tagged

Methods

bifold :: Monoid m => Tagged m m -> m #

bifoldMap :: Monoid m => (a -> m) -> (b -> m) -> Tagged a b -> m #

bifoldr :: (a -> c -> c) -> (b -> c -> c) -> c -> Tagged a b -> c #

bifoldl :: (c -> a -> c) -> (c -> b -> c) -> c -> Tagged a b -> c #

Bifunctor (Tagged :: Type -> Type -> Type) 
Instance details

Defined in Data.Tagged

Methods

bimap :: (a -> b) -> (c -> d) -> Tagged a c -> Tagged b d #

first :: (a -> b) -> Tagged a c -> Tagged b c #

second :: (b -> c) -> Tagged a b -> Tagged a c #

Eq2 (Tagged :: Type -> Type -> Type) 
Instance details

Defined in Data.Tagged

Methods

liftEq2 :: (a -> b -> Bool) -> (c -> d -> Bool) -> Tagged a c -> Tagged b d -> Bool #

Ord2 (Tagged :: Type -> Type -> Type) 
Instance details

Defined in Data.Tagged

Methods

liftCompare2 :: (a -> b -> Ordering) -> (c -> d -> Ordering) -> Tagged a c -> Tagged b d -> Ordering #

Read2 (Tagged :: Type -> Type -> Type) 
Instance details

Defined in Data.Tagged

Methods

liftReadsPrec2 :: (Int -> ReadS a) -> ReadS [a] -> (Int -> ReadS b) -> ReadS [b] -> Int -> ReadS (Tagged a b) #

liftReadList2 :: (Int -> ReadS a) -> ReadS [a] -> (Int -> ReadS b) -> ReadS [b] -> ReadS [Tagged a b] #

liftReadPrec2 :: ReadPrec a -> ReadPrec [a] -> ReadPrec b -> ReadPrec [b] -> ReadPrec (Tagged a b) #

liftReadListPrec2 :: ReadPrec a -> ReadPrec [a] -> ReadPrec b -> ReadPrec [b] -> ReadPrec [Tagged a b] #

Show2 (Tagged :: Type -> Type -> Type) 
Instance details

Defined in Data.Tagged

Methods

liftShowsPrec2 :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> (Int -> b -> ShowS) -> ([b] -> ShowS) -> Int -> Tagged a b -> ShowS #

liftShowList2 :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> (Int -> b -> ShowS) -> ([b] -> ShowS) -> [Tagged a b] -> ShowS #

Generic1 (Tagged s :: Type -> Type) 
Instance details

Defined in Data.Tagged

Associated Types

type Rep1 (Tagged s) :: k -> Type #

Methods

from1 :: Tagged s a -> Rep1 (Tagged s) a #

to1 :: Rep1 (Tagged s) a -> Tagged s a #

Monad (Tagged s) 
Instance details

Defined in Data.Tagged

Methods

(>>=) :: Tagged s a -> (a -> Tagged s b) -> Tagged s b #

(>>) :: Tagged s a -> Tagged s b -> Tagged s b #

return :: a -> Tagged s a #

fail :: String -> Tagged s a #

Functor (Tagged s) 
Instance details

Defined in Data.Tagged

Methods

fmap :: (a -> b) -> Tagged s a -> Tagged s b #

(<$) :: a -> Tagged s b -> Tagged s a #

Applicative (Tagged s) 
Instance details

Defined in Data.Tagged

Methods

pure :: a -> Tagged s a #

(<*>) :: Tagged s (a -> b) -> Tagged s a -> Tagged s b #

liftA2 :: (a -> b -> c) -> Tagged s a -> Tagged s b -> Tagged s c #

(*>) :: Tagged s a -> Tagged s b -> Tagged s b #

(<*) :: Tagged s a -> Tagged s b -> Tagged s a #

Foldable (Tagged s) 
Instance details

Defined in Data.Tagged

Methods

fold :: Monoid m => Tagged s m -> m #

foldMap :: Monoid m => (a -> m) -> Tagged s a -> m #

foldr :: (a -> b -> b) -> b -> Tagged s a -> b #

foldr' :: (a -> b -> b) -> b -> Tagged s a -> b #

foldl :: (b -> a -> b) -> b -> Tagged s a -> b #

foldl' :: (b -> a -> b) -> b -> Tagged s a -> b #

foldr1 :: (a -> a -> a) -> Tagged s a -> a #

foldl1 :: (a -> a -> a) -> Tagged s a -> a #

toList :: Tagged s a -> [a] #

null :: Tagged s a -> Bool #

length :: Tagged s a -> Int #

elem :: Eq a => a -> Tagged s a -> Bool #

maximum :: Ord a => Tagged s a -> a #

minimum :: Ord a => Tagged s a -> a #

sum :: Num a => Tagged s a -> a #

product :: Num a => Tagged s a -> a #

Traversable (Tagged s) 
Instance details

Defined in Data.Tagged

Methods

traverse :: Applicative f => (a -> f b) -> Tagged s a -> f (Tagged s b) #

sequenceA :: Applicative f => Tagged s (f a) -> f (Tagged s a) #

mapM :: Monad m => (a -> m b) -> Tagged s a -> m (Tagged s b) #

sequence :: Monad m => Tagged s (m a) -> m (Tagged s a) #

Eq1 (Tagged s) 
Instance details

Defined in Data.Tagged

Methods

liftEq :: (a -> b -> Bool) -> Tagged s a -> Tagged s b -> Bool #

Ord1 (Tagged s) 
Instance details

Defined in Data.Tagged

Methods

liftCompare :: (a -> b -> Ordering) -> Tagged s a -> Tagged s b -> Ordering #

Read1 (Tagged s) 
Instance details

Defined in Data.Tagged

Methods

liftReadsPrec :: (Int -> ReadS a) -> ReadS [a] -> Int -> ReadS (Tagged s a) #

liftReadList :: (Int -> ReadS a) -> ReadS [a] -> ReadS [Tagged s a] #

liftReadPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec (Tagged s a) #

liftReadListPrec :: ReadPrec a -> ReadPrec [a] -> ReadPrec [Tagged s a] #

Show1 (Tagged s) 
Instance details

Defined in Data.Tagged

Methods

liftShowsPrec :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> Tagged s a -> ShowS #

liftShowList :: (Int -> a -> ShowS) -> ([a] -> ShowS) -> [Tagged s a] -> ShowS #

Bounded b => Bounded (Tagged s b) 
Instance details

Defined in Data.Tagged

Methods

minBound :: Tagged s b #

maxBound :: Tagged s b #

Enum a => Enum (Tagged s a) 
Instance details

Defined in Data.Tagged

Methods

succ :: Tagged s a -> Tagged s a #

pred :: Tagged s a -> Tagged s a #

toEnum :: Int -> Tagged s a #

fromEnum :: Tagged s a -> Int #

enumFrom :: Tagged s a -> [Tagged s a] #

enumFromThen :: Tagged s a -> Tagged s a -> [Tagged s a] #

enumFromTo :: Tagged s a -> Tagged s a -> [Tagged s a] #

enumFromThenTo :: Tagged s a -> Tagged s a -> Tagged s a -> [Tagged s a] #

Eq b => Eq (Tagged s b) 
Instance details

Defined in Data.Tagged

Methods

(==) :: Tagged s b -> Tagged s b -> Bool #

(/=) :: Tagged s b -> Tagged s b -> Bool #

Floating a => Floating (Tagged s a) 
Instance details

Defined in Data.Tagged

Methods

pi :: Tagged s a #

exp :: Tagged s a -> Tagged s a #

log :: Tagged s a -> Tagged s a #

sqrt :: Tagged s a -> Tagged s a #

(**) :: Tagged s a -> Tagged s a -> Tagged s a #

logBase :: Tagged s a -> Tagged s a -> Tagged s a #

sin :: Tagged s a -> Tagged s a #

cos :: Tagged s a -> Tagged s a #

tan :: Tagged s a -> Tagged s a #

asin :: Tagged s a -> Tagged s a #

acos :: Tagged s a -> Tagged s a #

atan :: Tagged s a -> Tagged s a #

sinh :: Tagged s a -> Tagged s a #

cosh :: Tagged s a -> Tagged s a #

tanh :: Tagged s a -> Tagged s a #

asinh :: Tagged s a -> Tagged s a #

acosh :: Tagged s a -> Tagged s a #

atanh :: Tagged s a -> Tagged s a #

log1p :: Tagged s a -> Tagged s a #

expm1 :: Tagged s a -> Tagged s a #

log1pexp :: Tagged s a -> Tagged s a #

log1mexp :: Tagged s a -> Tagged s a #

Fractional a => Fractional (Tagged s a) 
Instance details

Defined in Data.Tagged

Methods

(/) :: Tagged s a -> Tagged s a -> Tagged s a #

recip :: Tagged s a -> Tagged s a #

fromRational :: Rational -> Tagged s a #

Integral a => Integral (Tagged s a) 
Instance details

Defined in Data.Tagged

Methods

quot :: Tagged s a -> Tagged s a -> Tagged s a #

rem :: Tagged s a -> Tagged s a -> Tagged s a #

div :: Tagged s a -> Tagged s a -> Tagged s a #

mod :: Tagged s a -> Tagged s a -> Tagged s a #

quotRem :: Tagged s a -> Tagged s a -> (Tagged s a, Tagged s a) #

divMod :: Tagged s a -> Tagged s a -> (Tagged s a, Tagged s a) #

toInteger :: Tagged s a -> Integer #

(Data s, Data b) => Data (Tagged s b) 
Instance details

Defined in Data.Tagged

Methods

gfoldl :: (forall d b0. Data d => c (d -> b0) -> d -> c b0) -> (forall g. g -> c g) -> Tagged s b -> c (Tagged s b) #

gunfold :: (forall b0 r. Data b0 => c (b0 -> r) -> c r) -> (forall r. r -> c r) -> Constr -> c (Tagged s b) #

toConstr :: Tagged s b -> Constr #

dataTypeOf :: Tagged s b -> DataType #

dataCast1 :: Typeable t => (forall d. Data d => c (t d)) -> Maybe (c (Tagged s b)) #

dataCast2 :: Typeable t => (forall d e. (Data d, Data e) => c (t d e)) -> Maybe (c (Tagged s b)) #

gmapT :: (forall b0. Data b0 => b0 -> b0) -> Tagged s b -> Tagged s b #

gmapQl :: (r -> r' -> r) -> r -> (forall d. Data d => d -> r') -> Tagged s b -> r #

gmapQr :: (r' -> r -> r) -> r -> (forall d. Data d => d -> r') -> Tagged s b -> r #

gmapQ :: (forall d. Data d => d -> u) -> Tagged s b -> [u] #

gmapQi :: Int -> (forall d. Data d => d -> u) -> Tagged s b -> u #

gmapM :: Monad m => (forall d. Data d => d -> m d) -> Tagged s b -> m (Tagged s b) #

gmapMp :: MonadPlus m => (forall d. Data d => d -> m d) -> Tagged s b -> m (Tagged s b) #

gmapMo :: MonadPlus m => (forall d. Data d => d -> m d) -> Tagged s b -> m (Tagged s b) #

Num a => Num (Tagged s a) 
Instance details

Defined in Data.Tagged

Methods

(+) :: Tagged s a -> Tagged s a -> Tagged s a #

(-) :: Tagged s a -> Tagged s a -> Tagged s a #

(*) :: Tagged s a -> Tagged s a -> Tagged s a #

negate :: Tagged s a -> Tagged s a #

abs :: Tagged s a -> Tagged s a #

signum :: Tagged s a -> Tagged s a #

fromInteger :: Integer -> Tagged s a #

Ord b => Ord (Tagged s b) 
Instance details

Defined in Data.Tagged

Methods

compare :: Tagged s b -> Tagged s b -> Ordering #

(<) :: Tagged s b -> Tagged s b -> Bool #

(<=) :: Tagged s b -> Tagged s b -> Bool #

(>) :: Tagged s b -> Tagged s b -> Bool #

(>=) :: Tagged s b -> Tagged s b -> Bool #

max :: Tagged s b -> Tagged s b -> Tagged s b #

min :: Tagged s b -> Tagged s b -> Tagged s b #

Read b => Read (Tagged s b) 
Instance details

Defined in Data.Tagged

Real a => Real (Tagged s a) 
Instance details

Defined in Data.Tagged

Methods

toRational :: Tagged s a -> Rational #

RealFloat a => RealFloat (Tagged s a) 
Instance details

Defined in Data.Tagged

Methods

floatRadix :: Tagged s a -> Integer #

floatDigits :: Tagged s a -> Int #

floatRange :: Tagged s a -> (Int, Int) #

decodeFloat :: Tagged s a -> (Integer, Int) #

encodeFloat :: Integer -> Int -> Tagged s a #

exponent :: Tagged s a -> Int #

significand :: Tagged s a -> Tagged s a #

scaleFloat :: Int -> Tagged s a -> Tagged s a #

isNaN :: Tagged s a -> Bool #

isInfinite :: Tagged s a -> Bool #

isDenormalized :: Tagged s a -> Bool #

isNegativeZero :: Tagged s a -> Bool #

isIEEE :: Tagged s a -> Bool #

atan2 :: Tagged s a -> Tagged s a -> Tagged s a #

RealFrac a => RealFrac (Tagged s a) 
Instance details

Defined in Data.Tagged

Methods

properFraction :: Integral b => Tagged s a -> (b, Tagged s a) #

truncate :: Integral b => Tagged s a -> b #

round :: Integral b => Tagged s a -> b #

ceiling :: Integral b => Tagged s a -> b #

floor :: Integral b => Tagged s a -> b #

Show b => Show (Tagged s b) 
Instance details

Defined in Data.Tagged

Methods

showsPrec :: Int -> Tagged s b -> ShowS #

show :: Tagged s b -> String #

showList :: [Tagged s b] -> ShowS #

Ix b => Ix (Tagged s b) 
Instance details

Defined in Data.Tagged

Methods

range :: (Tagged s b, Tagged s b) -> [Tagged s b] #

index :: (Tagged s b, Tagged s b) -> Tagged s b -> Int #

unsafeIndex :: (Tagged s b, Tagged s b) -> Tagged s b -> Int

inRange :: (Tagged s b, Tagged s b) -> Tagged s b -> Bool #

rangeSize :: (Tagged s b, Tagged s b) -> Int #

unsafeRangeSize :: (Tagged s b, Tagged s b) -> Int

IsString a => IsString (Tagged s a) 
Instance details

Defined in Data.Tagged

Methods

fromString :: String -> Tagged s a #

Generic (Tagged s b) 
Instance details

Defined in Data.Tagged

Associated Types

type Rep (Tagged s b) :: Type -> Type #

Methods

from :: Tagged s b -> Rep (Tagged s b) x #

to :: Rep (Tagged s b) x -> Tagged s b #

Semigroup a => Semigroup (Tagged s a) 
Instance details

Defined in Data.Tagged

Methods

(<>) :: Tagged s a -> Tagged s a -> Tagged s a #

sconcat :: NonEmpty (Tagged s a) -> Tagged s a #

stimes :: Integral b => b -> Tagged s a -> Tagged s a #

(Semigroup a, Monoid a) => Monoid (Tagged s a) 
Instance details

Defined in Data.Tagged

Methods

mempty :: Tagged s a #

mappend :: Tagged s a -> Tagged s a -> Tagged s a #

mconcat :: [Tagged s a] -> Tagged s a #

Storable a => Storable (Tagged s a) 
Instance details

Defined in Data.Tagged

Methods

sizeOf :: Tagged s a -> Int #

alignment :: Tagged s a -> Int #

peekElemOff :: Ptr (Tagged s a) -> Int -> IO (Tagged s a) #

pokeElemOff :: Ptr (Tagged s a) -> Int -> Tagged s a -> IO () #

peekByteOff :: Ptr b -> Int -> IO (Tagged s a) #

pokeByteOff :: Ptr b -> Int -> Tagged s a -> IO () #

peek :: Ptr (Tagged s a) -> IO (Tagged s a) #

poke :: Ptr (Tagged s a) -> Tagged s a -> IO () #

Bits a => Bits (Tagged s a) 
Instance details

Defined in Data.Tagged

Methods

(.&.) :: Tagged s a -> Tagged s a -> Tagged s a #

(.|.) :: Tagged s a -> Tagged s a -> Tagged s a #

xor :: Tagged s a -> Tagged s a -> Tagged s a #

complement :: Tagged s a -> Tagged s a #

shift :: Tagged s a -> Int -> Tagged s a #

rotate :: Tagged s a -> Int -> Tagged s a #

zeroBits :: Tagged s a #

bit :: Int -> Tagged s a #

setBit :: Tagged s a -> Int -> Tagged s a #

clearBit :: Tagged s a -> Int -> Tagged s a #

complementBit :: Tagged s a -> Int -> Tagged s a #

testBit :: Tagged s a -> Int -> Bool #

bitSizeMaybe :: Tagged s a -> Maybe Int #

bitSize :: Tagged s a -> Int #

isSigned :: Tagged s a -> Bool #

shiftL :: Tagged s a -> Int -> Tagged s a #

unsafeShiftL :: Tagged s a -> Int -> Tagged s a #

shiftR :: Tagged s a -> Int -> Tagged s a #

unsafeShiftR :: Tagged s a -> Int -> Tagged s a #

rotateL :: Tagged s a -> Int -> Tagged s a #

rotateR :: Tagged s a -> Int -> Tagged s a #

popCount :: Tagged s a -> Int #

FiniteBits a => FiniteBits (Tagged s a) 
Instance details

Defined in Data.Tagged

NFData b => NFData (Tagged s b) 
Instance details

Defined in Data.Tagged

Methods

rnf :: Tagged s b -> () #

Finite a => Finite (Tagged b a) Source # 
Instance details

Defined in Data.Universe.Class

Universe a => Universe (Tagged b a) Source # 
Instance details

Defined in Data.Universe.Class

Methods

universe :: [Tagged b a] Source #

type Rep1 (Tagged s :: Type -> Type) 
Instance details

Defined in Data.Tagged

type Rep1 (Tagged s :: Type -> Type) = D1 (MetaData "Tagged" "Data.Tagged" "tagged-0.8.6-FABECvKnqYbBCttH1EeJvB" True) (C1 (MetaCons "Tagged" PrefixI True) (S1 (MetaSel (Just "unTagged") NoSourceUnpackedness NoSourceStrictness DecidedLazy) Par1))
type Rep (Tagged s b) 
Instance details

Defined in Data.Tagged

type Rep (Tagged s b) = D1 (MetaData "Tagged" "Data.Tagged" "tagged-0.8.6-FABECvKnqYbBCttH1EeJvB" True) (C1 (MetaCons "Tagged" PrefixI True) (S1 (MetaSel (Just "unTagged") NoSourceUnpackedness NoSourceStrictness DecidedLazy) (Rec0 b)))

data Natural #

Type representing arbitrary-precision non-negative integers.

>>> 2^100 :: Natural
1267650600228229401496703205376

Operations whose result would be negative throw (Underflow :: ArithException),

>>> -1 :: Natural
*** Exception: arithmetic underflow

Since: base-4.8.0.0

Instances
Enum Natural

Since: base-4.8.0.0

Instance details

Defined in GHC.Enum

Eq Natural

Since: base-4.8.0.0

Instance details

Defined in GHC.Natural

Methods

(==) :: Natural -> Natural -> Bool #

(/=) :: Natural -> Natural -> Bool #

Integral Natural

Since: base-4.8.0.0

Instance details

Defined in GHC.Real

Num Natural

Note that Natural's Num instance isn't a ring: no element but 0 has an additive inverse. It is a semiring though.

Since: base-4.8.0.0

Instance details

Defined in GHC.Num

Ord Natural

Since: base-4.8.0.0

Instance details

Defined in GHC.Natural

Read Natural

Since: base-4.8.0.0

Instance details

Defined in GHC.Read

Real Natural

Since: base-4.8.0.0

Instance details

Defined in GHC.Real

Show Natural

Since: base-4.8.0.0

Instance details

Defined in GHC.Show

Universe Natural Source # 
Instance details

Defined in Data.Universe.Class

Methods

universe :: [Natural] Source #

Debugging

These functions exist primarily as a specification to test against.

unfairCartesianProduct :: (a -> b -> c) -> [a] -> [b] -> [c] Source #

Very unfair 2-way Cartesian product: same guarantee as the slightly unfair one, except that lower indices may occur as the fst part of the tuple exponentially more frequently.

unfairChoices :: [[a]] -> [[a]] Source #

Very unfair n-way Cartesian product: same guarantee as the slightly unfair one, but not as good in the same sense that the very unfair 2-way product is worse than the slightly unfair 2-way product.