-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/

-- | A class for finite and recursively enumerable types.
--   
--   A class for finite and recursively enumerable types and some helper
--   functions for enumerating them.
--   
--   
--   class Universe a where universe :: [a]
--   class Universe a => Finite a where universeF :: [a]; universeF = universe
--   
--   
--   This is slim package definiting only the type-classes and instances
--   for types in GHC boot libraries. For more instances check
--   universe-instances-* packages.
@package universe-base
@version 1.1.4

module Data.Universe.Helpers

-- | 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
--   
universeDef :: (Bounded a, Enum a) => [a]

-- | 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.
interleave :: [[a]] -> [a]

-- | 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.
diagonal :: [[a]] -> [a]

-- | 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.
diagonals :: [[a]] -> [[a]]

-- | Fair 2-way interleaving.
(+++) :: [a] -> [a] -> [a]

-- | 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.
cartesianProduct :: (a -> b -> c) -> [a] -> [b] -> [c]

-- | 
--   cartesianProduct (,)
--   
(+*+) :: [a] -> [b] -> [(a, b)]

-- | A +*+ with application.
--   
--   
--   cartesianProduct ($)
--   
(<+*+>) :: [a -> b] -> [a] -> [b]

-- | 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.
choices :: [[a]] -> [[a]]
retagWith :: (a -> b) -> Tagged a x -> Tagged b x

-- | 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
--   
retag :: forall {k1} {k2} (s :: k1) b (t :: k2). Tagged s b -> Tagged t b

-- | 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.
newtype Tagged (s :: k) b
Tagged :: b -> Tagged (s :: k) b
[unTagged] :: Tagged (s :: k) b -> b

-- | Natural number
--   
--   Invariant: numbers <= 0xffffffffffffffff use the NS
--   constructor
data Natural

-- | 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.
unfairCartesianProduct :: (a -> b -> c) -> [a] -> [b] -> [c]

-- | 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.
unfairChoices :: [[a]] -> [[a]]

-- | Bottoms are ignored for this entire module: only fully-defined
--   inhabitants are considered inhabitants.
module Data.Universe.Class

-- | Creating an instance of this class is a declaration that your type is
--   recursively enumerable (and that universe is that enumeration).
--   In particular, you promise that any finite inhabitant has a finite
--   index in universe, and that no inhabitant appears at two
--   different finite indices.
--   
--   Well-behaved instance should produce elements lazily.
--   
--   Laws:
--   
--   
--   elem x universe                    -- any inhabitant has a finite index
--   let pfx = take n universe          -- any finite prefix of universe has unique elements
--   in length pfx = length (nub pfx)
--   
class Universe a
universe :: Universe a => [a]
($dmuniverse) :: (Universe a, Enum a, Bounded a) => [a]

-- | Creating an instance of this class is a declaration that your
--   universe eventually ends. Minimal definition: no methods
--   defined. By default, universeF = universe, but for some types
--   (like Either) the universeF method may have a more
--   intuitive ordering.
--   
--   Laws:
--   
--   
--   elem x universeF                       -- any inhabitant has a finite index
--   length (filter (== x) universeF) == 1  -- should terminate
--   (xs -> cardinality xs == genericLength xs) universeF
--   
--   
--   Note: elemIndex x universe ==
--   elemIndex x universeF may not hold for all types,
--   though the laws imply that universe is a permutation of
--   universeF.
--   
--   
--   >>> elemIndex (Left True :: Either Bool Bool) universe
--   Just 2
--   
--   
--   
--   >>> elemIndex (Left True :: Either Bool Bool) universeF
--   Just 1
--   
class Universe a => Finite a
universeF :: Finite a => [a]
cardinality :: Finite a => Tagged a Natural
instance Data.Universe.Class.Finite GHC.Internal.Data.Semigroup.Internal.All
instance Data.Universe.Class.Finite GHC.Internal.Data.Semigroup.Internal.Any
instance Data.Universe.Class.Finite GHC.Types.Bool
instance Data.Universe.Class.Finite GHC.Types.Char
instance Data.Universe.Class.Finite (f (g a)) => Data.Universe.Class.Finite (Data.Functor.Compose.Compose f g a)
instance Data.Universe.Class.Finite a => Data.Universe.Class.Finite (GHC.Internal.Data.Functor.Const.Const a b)
instance Data.Universe.Class.Finite a => Data.Universe.Class.Finite (GHC.Internal.Data.Semigroup.Internal.Dual a)
instance (Data.Universe.Class.Finite a, Data.Universe.Class.Finite b) => Data.Universe.Class.Finite (GHC.Internal.Data.Either.Either a b)
instance (GHC.Classes.Ord a, Data.Universe.Class.Finite a, Data.Universe.Class.Finite b) => Data.Universe.Class.Finite (a -> b)
instance Data.Universe.Class.Finite a => Data.Universe.Class.Finite (Data.Semigroup.First a)
instance Data.Universe.Class.Finite a => Data.Universe.Class.Finite (GHC.Internal.Data.Monoid.First a)
instance Data.Universe.Class.Finite a => Data.Universe.Class.Finite (GHC.Internal.Data.Functor.Identity.Identity a)
instance Data.Universe.Class.Finite (f a) => Data.Universe.Class.Finite (Control.Monad.Trans.Identity.IdentityT f a)
instance Data.Universe.Class.Finite GHC.Types.Int
instance Data.Universe.Class.Finite GHC.Internal.Int.Int16
instance Data.Universe.Class.Finite GHC.Internal.Int.Int32
instance Data.Universe.Class.Finite GHC.Internal.Int.Int64
instance Data.Universe.Class.Finite GHC.Internal.Int.Int8
instance Data.Universe.Class.Finite a => Data.Universe.Class.Finite (Data.Semigroup.Last a)
instance Data.Universe.Class.Finite a => Data.Universe.Class.Finite (GHC.Internal.Data.Monoid.Last a)
instance (GHC.Classes.Ord k, Data.Universe.Class.Finite k, Data.Universe.Class.Finite v) => Data.Universe.Class.Finite (Data.Map.Internal.Map k v)
instance Data.Universe.Class.Finite a => Data.Universe.Class.Finite (Data.Semigroup.Max a)
instance Data.Universe.Class.Finite a => Data.Universe.Class.Finite (GHC.Internal.Maybe.Maybe a)
instance Data.Universe.Class.Finite a => Data.Universe.Class.Finite (Data.Semigroup.Min a)
instance Data.Universe.Class.Finite GHC.Types.Ordering
instance (Data.Universe.Class.Finite (f a), Data.Universe.Class.Finite (g a)) => Data.Universe.Class.Finite (Data.Functor.Product.Product f g a)
instance Data.Universe.Class.Finite a => Data.Universe.Class.Finite (GHC.Internal.Data.Semigroup.Internal.Product a)
instance Data.Universe.Class.Finite (GHC.Internal.Data.Proxy.Proxy a)
instance (Data.Universe.Class.Finite e, GHC.Classes.Ord e, Data.Universe.Class.Finite (m a)) => Data.Universe.Class.Finite (Control.Monad.Trans.Reader.ReaderT e m a)
instance (GHC.Classes.Ord a, Data.Universe.Class.Finite a) => Data.Universe.Class.Finite (Data.Set.Internal.Set a)
instance Data.Universe.Class.Finite a => Data.Universe.Class.Finite (GHC.Tuple.Solo a)
instance (Data.Universe.Class.Finite (f a), Data.Universe.Class.Finite (g a)) => Data.Universe.Class.Finite (Data.Functor.Sum.Sum f g a)
instance Data.Universe.Class.Finite a => Data.Universe.Class.Finite (GHC.Internal.Data.Semigroup.Internal.Sum a)
instance Data.Universe.Class.Finite a => Data.Universe.Class.Finite (Data.Tagged.Tagged b a)
instance (Data.Universe.Class.Finite a, Data.Universe.Class.Finite b) => Data.Universe.Class.Finite (a, b)
instance (Data.Universe.Class.Finite a, Data.Universe.Class.Finite b, Data.Universe.Class.Finite c) => Data.Universe.Class.Finite (a, b, c)
instance (Data.Universe.Class.Finite a, Data.Universe.Class.Finite b, Data.Universe.Class.Finite c, Data.Universe.Class.Finite d) => Data.Universe.Class.Finite (a, b, c, d)
instance (Data.Universe.Class.Finite a, Data.Universe.Class.Finite b, Data.Universe.Class.Finite c, Data.Universe.Class.Finite d, Data.Universe.Class.Finite e) => Data.Universe.Class.Finite (a, b, c, d, e)
instance Data.Universe.Class.Finite ()
instance Data.Universe.Class.Finite GHC.Internal.Base.Void
instance Data.Universe.Class.Finite GHC.Types.Word
instance Data.Universe.Class.Finite GHC.Internal.Word.Word16
instance Data.Universe.Class.Finite GHC.Internal.Word.Word32
instance Data.Universe.Class.Finite GHC.Internal.Word.Word64
instance Data.Universe.Class.Finite GHC.Internal.Word.Word8
instance Data.Universe.Class.RationalUniverse GHC.Num.Integer.Integer
instance Data.Universe.Class.RationalUniverse GHC.Num.Natural.Natural
instance Data.Universe.Class.Universe GHC.Internal.Data.Semigroup.Internal.All
instance Data.Universe.Class.Universe GHC.Internal.Data.Semigroup.Internal.Any
instance Data.Universe.Class.Universe GHC.Types.Bool
instance Data.Universe.Class.Universe GHC.Types.Char
instance Data.Universe.Class.Universe (f (g a)) => Data.Universe.Class.Universe (Data.Functor.Compose.Compose f g a)
instance Data.Universe.Class.Universe a => Data.Universe.Class.Universe (GHC.Internal.Data.Functor.Const.Const a b)
instance Data.Universe.Class.Universe a => Data.Universe.Class.Universe (GHC.Internal.Data.Semigroup.Internal.Dual a)
instance (Data.Universe.Class.Universe a, Data.Universe.Class.Universe b) => Data.Universe.Class.Universe (GHC.Internal.Data.Either.Either a b)
instance (Data.Universe.Class.Finite a, GHC.Classes.Ord a, Data.Universe.Class.Universe b) => Data.Universe.Class.Universe (a -> b)
instance Data.Universe.Class.Universe a => Data.Universe.Class.Universe (Data.Semigroup.First a)
instance Data.Universe.Class.Universe a => Data.Universe.Class.Universe (GHC.Internal.Data.Monoid.First a)
instance Data.Universe.Class.Universe a => Data.Universe.Class.Universe (GHC.Internal.Data.Functor.Identity.Identity a)
instance Data.Universe.Class.Universe (f a) => Data.Universe.Class.Universe (Control.Monad.Trans.Identity.IdentityT f a)
instance Data.Universe.Class.Universe GHC.Types.Int
instance Data.Universe.Class.Universe GHC.Internal.Int.Int16
instance Data.Universe.Class.Universe GHC.Internal.Int.Int32
instance Data.Universe.Class.Universe GHC.Internal.Int.Int64
instance Data.Universe.Class.Universe GHC.Internal.Int.Int8
instance Data.Universe.Class.Universe GHC.Num.Integer.Integer
instance Data.Universe.Class.Universe a => Data.Universe.Class.Universe (Data.Semigroup.Last a)
instance Data.Universe.Class.Universe a => Data.Universe.Class.Universe (GHC.Internal.Data.Monoid.Last a)
instance Data.Universe.Class.Universe a => Data.Universe.Class.Universe [a]
instance (GHC.Classes.Ord k, Data.Universe.Class.Finite k, Data.Universe.Class.Universe v) => Data.Universe.Class.Universe (Data.Map.Internal.Map k v)
instance Data.Universe.Class.Universe a => Data.Universe.Class.Universe (Data.Semigroup.Max a)
instance Data.Universe.Class.Universe a => Data.Universe.Class.Universe (GHC.Internal.Maybe.Maybe a)
instance Data.Universe.Class.Universe a => Data.Universe.Class.Universe (Data.Semigroup.Min a)
instance Data.Universe.Class.Universe GHC.Num.Natural.Natural
instance Data.Universe.Class.Universe a => Data.Universe.Class.Universe (GHC.Internal.Base.NonEmpty a)
instance Data.Universe.Class.Universe GHC.Types.Ordering
instance (Data.Universe.Class.Universe (f a), Data.Universe.Class.Universe (g a)) => Data.Universe.Class.Universe (Data.Functor.Product.Product f g a)
instance Data.Universe.Class.Universe a => Data.Universe.Class.Universe (GHC.Internal.Data.Semigroup.Internal.Product a)
instance Data.Universe.Class.Universe (GHC.Internal.Data.Proxy.Proxy a)
instance Data.Universe.Class.RationalUniverse a => Data.Universe.Class.Universe (GHC.Internal.Real.Ratio a)
instance (Data.Universe.Class.Finite e, GHC.Classes.Ord e, Data.Universe.Class.Universe (m a)) => Data.Universe.Class.Universe (Control.Monad.Trans.Reader.ReaderT e m a)
instance (GHC.Classes.Ord a, Data.Universe.Class.Universe a) => Data.Universe.Class.Universe (Data.Set.Internal.Set a)
instance Data.Universe.Class.Universe a => Data.Universe.Class.Universe (GHC.Tuple.Solo a)
instance (Data.Universe.Class.Universe (f a), Data.Universe.Class.Universe (g a)) => Data.Universe.Class.Universe (Data.Functor.Sum.Sum f g a)
instance Data.Universe.Class.Universe a => Data.Universe.Class.Universe (GHC.Internal.Data.Semigroup.Internal.Sum a)
instance Data.Universe.Class.Universe a => Data.Universe.Class.Universe (Data.Tagged.Tagged b a)
instance (Data.Universe.Class.Universe a, Data.Universe.Class.Universe b) => Data.Universe.Class.Universe (a, b)
instance (Data.Universe.Class.Universe a, Data.Universe.Class.Universe b, Data.Universe.Class.Universe c) => Data.Universe.Class.Universe (a, b, c)
instance (Data.Universe.Class.Universe a, Data.Universe.Class.Universe b, Data.Universe.Class.Universe c, Data.Universe.Class.Universe d) => Data.Universe.Class.Universe (a, b, c, d)
instance (Data.Universe.Class.Universe a, Data.Universe.Class.Universe b, Data.Universe.Class.Universe c, Data.Universe.Class.Universe d, Data.Universe.Class.Universe e) => Data.Universe.Class.Universe (a, b, c, d, e)
instance Data.Universe.Class.Universe ()
instance Data.Universe.Class.Universe GHC.Internal.Base.Void
instance Data.Universe.Class.Universe GHC.Types.Word
instance Data.Universe.Class.Universe GHC.Internal.Word.Word16
instance Data.Universe.Class.Universe GHC.Internal.Word.Word32
instance Data.Universe.Class.Universe GHC.Internal.Word.Word64
instance Data.Universe.Class.Universe GHC.Internal.Word.Word8

module Data.Universe.Generic
class GUniverse (f :: Type -> Type)
guniverse :: GUniverse f => [f a]
class GUniverseSum (f :: Type -> Type)
guniverseSum :: GUniverseSum f => [[f a]]
class GUniverseProduct (f :: Type -> Type)
guniverseProduct :: GUniverseProduct f => [f a]

-- | 
--   >>> data One = One deriving (Show, Generic)
--   
--   >>> universeGeneric :: [One]
--   [One]
--   
--   
--   
--   >>> data Big = B0 Bool Bool | B1 Bool deriving (Show, Generic)
--   
--   >>> universeGeneric :: [Big]
--   [B0 False False,B1 False,B0 False True,B1 True,B0 True False,B0 True True]
--   
--   
--   
--   >>> universeGeneric :: [Maybe Ordering]
--   [Nothing,Just LT,Just EQ,Just GT]
--   
--   
--   
--   >>> take 10 (universeGeneric :: [Either Integer Integer])
--   [Left 0,Right 0,Left 1,Right 1,Left (-1),Right (-1),Left 2,Right 2,Left (-2),Right (-2)]
--   
--   
--   
--   >>> take 10 (universeGeneric :: [(Integer, Integer, Integer)])
--   [(0,0,0),(0,0,1),(1,0,0),(0,1,0),(1,0,1),(-1,0,0),(0,0,-1),(1,1,0),(-1,0,1),(2,0,0)]
--   
universeGeneric :: (Generic a, GUniverse (Rep a)) => [a]
instance Data.Universe.Generic.GUniverseSum f => Data.Universe.Generic.GUniverse (GHC.Internal.Generics.M1 i c f)
instance (Data.Universe.Generic.GUniverseProduct f, Data.Universe.Generic.GUniverseProduct g) => Data.Universe.Generic.GUniverseProduct (f GHC.Internal.Generics.:*: g)
instance Data.Universe.Class.Universe a => Data.Universe.Generic.GUniverseProduct (GHC.Internal.Generics.K1 r a)
instance Data.Universe.Generic.GUniverseProduct f => Data.Universe.Generic.GUniverseProduct (GHC.Internal.Generics.M1 i c f)
instance Data.Universe.Generic.GUniverseProduct GHC.Internal.Generics.U1
instance (Data.Universe.Generic.GUniverseSum f, Data.Universe.Generic.GUniverseSum g) => Data.Universe.Generic.GUniverseSum (f GHC.Internal.Generics.:+: g)
instance Data.Universe.Generic.GUniverseProduct f => Data.Universe.Generic.GUniverseSum (GHC.Internal.Generics.M1 i c f)
instance Data.Universe.Generic.GUniverseSum GHC.Internal.Generics.V1
