-- 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.
--   
--   <pre>
--   class Universe a where universe :: [a]
--   class Universe a =&gt; Finite a where universeF :: [a]; universeF = universe
--   </pre>
--   
--   This is slim package definiting only the type-classes and instances
--   for types in GHC boot libraries. For more instances check
--   <tt>universe-instances-*</tt> packages.
@package universe-base
@version 1.1.3.1

module Data.Universe.Helpers

-- | For many types, the <tt>universe</tt> should be <tt>[minBound ..
--   maxBound]</tt>; <a>universeDef</a> makes it easy to make such types an
--   instance of <tt>Universe</tt> via the snippet
--   
--   <pre>
--   instance Universe Foo where universe = universeDef
--   </pre>
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 <tt>v</tt> has finite
--   index in one of the input lists, <tt>v</tt> 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
--   <tt>v</tt> has finite index in an input list at finite index,
--   <tt>v</tt> 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 <a>diagonal</a>, 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 <tt>v</tt> and
--   <tt>w</tt> have finite indices in the input lists, <tt>(v,w)</tt> has
--   finite index in the output list. Lower indices occur as the
--   <tt>fst</tt> part of the tuple more frequently, but not exponentially
--   so.
cartesianProduct :: (a -> b -> c) -> [a] -> [b] -> [c]

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

-- | A <a>+*+</a> with application.
--   
--   <pre>
--   <a>cartesianProduct</a> ($)
--   </pre>
(<+*+>) :: [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
--   <tt>vi</tt> has finite index in list i for each i, <tt>[v1, ...,
--   vn]</tt> 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
--   <a>retag</a>.
--   
--   <pre>
--   data Succ n
--   retagSucc :: <a>Tagged</a> n a -&gt; <a>Tagged</a> (Succ n) a
--   retagSucc = <a>retag</a>
--   </pre>
retag :: forall {k1} {k2} (s :: k1) b (t :: k2). Tagged s b -> Tagged t b

-- | A <tt><a>Tagged</a> s b</tt> value is a value <tt>b</tt> with an
--   attached phantom type <tt>s</tt>. 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 <tt>(s -&gt; b)</tt>, a
--   <tt><a>Tagged</a> s b</tt> can't try to use the argument <tt>s</tt> 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"
--   
--   <a>Tagged</a> has kind <tt>k -&gt; * -&gt; *</tt> if the compiler
--   supports <tt>PolyKinds</tt>, therefore there is an extra <tt>k</tt>
--   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 &lt;= 0xffffffffffffffff use the <a>NS</a>
--   constructor
data () => Natural

-- | Very unfair 2-way Cartesian product: same guarantee as the slightly
--   unfair one, except that lower indices may occur as the <tt>fst</tt>
--   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 <a>universe</a> is that enumeration).
--   In particular, you promise that any finite inhabitant has a finite
--   index in <a>universe</a>, and that no inhabitant appears at two
--   different finite indices.
--   
--   Well-behaved instance should produce elements lazily.
--   
--   <i>Laws:</i>
--   
--   <pre>
--   <a>elem</a> x <a>universe</a>                    -- any inhabitant has a finite index
--   let pfx = <a>take</a> n <a>universe</a>          -- any finite prefix of universe has unique elements
--   in <a>length</a> pfx = <a>length</a> (nub pfx)
--   </pre>
class Universe a
universe :: Universe a => [a]
universe :: (Universe a, Enum a, Bounded a) => [a]

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

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

-- | <pre>
--   &gt;&gt;&gt; data One = One deriving (Show, Generic)
--   
--   &gt;&gt;&gt; universeGeneric :: [One]
--   [One]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; data Big = B0 Bool Bool | B1 Bool deriving (Show, Generic)
--   
--   &gt;&gt;&gt; universeGeneric :: [Big]
--   [B0 False False,B1 False,B0 False True,B1 True,B0 True False,B0 True True]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; universeGeneric :: [Maybe Ordering]
--   [Nothing,Just LT,Just EQ,Just GT]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&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)]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; 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)]
--   </pre>
universeGeneric :: (Generic a, GUniverse (Rep a)) => [a]
instance Data.Universe.Generic.GUniverseProduct f => Data.Universe.Generic.GUniverseSum (GHC.Generics.M1 i c f)
instance Data.Universe.Generic.GUniverseProduct GHC.Generics.U1
instance (Data.Universe.Generic.GUniverseProduct f, Data.Universe.Generic.GUniverseProduct g) => Data.Universe.Generic.GUniverseProduct (f GHC.Generics.:*: g)
instance Data.Universe.Generic.GUniverseProduct f => Data.Universe.Generic.GUniverseProduct (GHC.Generics.M1 i c f)
instance Data.Universe.Class.Universe a => Data.Universe.Generic.GUniverseProduct (GHC.Generics.K1 r a)
instance Data.Universe.Generic.GUniverseSum f => Data.Universe.Generic.GUniverse (GHC.Generics.M1 i c f)
instance Data.Universe.Generic.GUniverseSum GHC.Generics.V1
instance (Data.Universe.Generic.GUniverseSum f, Data.Universe.Generic.GUniverseSum g) => Data.Universe.Generic.GUniverseSum (f GHC.Generics.:+: g)
