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


-- | Sized functors, for size-based enumerations
--   
--   A framework for size-based enumerations. See the module documentation
--   for details.
@package size-based
@version 0.1.3.0


-- | This module provides the <a>Sized</a> class. Instances of this class
--   are typically collection data types for infinite sets of values with a
--   finite number of values of any given size.
--   
--   A simple example is <a>Control.Enumerable.Count</a> that just counts
--   the number of values of each size. <a>Control.Enumerable.Values</a>
--   provides all values of a given size. <a>FEAT</a> provides any value in
--   the set much more efficiently.
module Control.Sized

-- | A sized functor is an applicative functor extended with a notion of
--   cost/size of contained values. This is useful for any type of bounded
--   recursion over infinite sets, most notably for various kind of
--   enumerations.
--   
--   The intention is that every sized functor definition models a
--   (usually) infinite set (technically a bag) with a finite number of
--   values of any given size. As long as every cyclic (recursive)
--   definition has at least one application of pay, this invariant is
--   guaranteed.
--   
--   The module <a>Control.Enumerable</a> provides sized functor
--   definitions for a lot of data types, such that the size of a value is
--   the number of constructor applications it contains. It also allows
--   deriving these functors for any user defined data type (using Template
--   Haskell).
class Alternative f => Sized f

-- | Increases the cost/size of all values in the given set.
pay :: Sized f => f a -> f a

-- | Default: <tt>pair a b = (,) <a>$</a> a <a>*</a> b</tt>.
pair :: Sized f => f a -> f b -> f (a, b)

-- | Default: <tt>aconcat = foldr (&lt;|&gt;) empty</tt>
aconcat :: Sized f => [f a] -> f a

-- | Finite numeric types. <tt>fin n</tt> contains all non-negative numbers
--   below n. This definition is flat, all integers have the same size.
--   Implementing this function efficiently will have a great impact on
--   applications that use a lot of bounded numeric types (e.g. Int).
--   
--   Default: aconcat (map pure [0..n-1])
fin :: Sized f => Integer -> f Integer

-- | Same as <a>fin</a> but the size of values may differ. By default, the
--   size of an integer is the number of significant bits in its binary
--   representation. In other words, 0 has size zero, the values for size
--   k&gt;0 in <tt>finBits n</tt> are in the interval <tt>(2^(k-1),min
--   (2^k-1) n)</tt>.
finSized :: Sized f => Integer -> f Integer

-- | Non-negative integers. By default, the size of an integer is the
--   number of digits in its binary representation.
naturals :: Sized f => f Integer
kbits :: Sized f => Int -> f Integer


-- | This module provides the <a>Enumerable</a> class, which has a simple
--   purpose: Provide any enumeration for any instance type. The
--   prerequisite is that the enumeration data type is a sized functor (see
--   <a>Control.Sized</a>) with the enumerated type as the type parameter.
--   The general idea is that the size of a value is the number of
--   constructor applications it contains.
--   
--   Because Sized functors often rely of memoization, sharing is
--   important. Since class dictionaries are not always shared, a mechanism
--   is added that guarantees optimal sharing (it never creates two
--   separate instance members for the same type). This is why the type of
--   <a>enumerate</a> is <tt>Shared f a</tt> instead of simply <tt>f
--   a</tt>. The technicalities of this memoization are not important, but
--   it means there are two modes for accessing an enumeration:
--   <a>local</a> and <a>global</a>. The former means sharing is guaranteed
--   within this value, but subsequent calls to local may recreate
--   dictionaries. The latter guarantees optimal sharing even between
--   calls. It also means the enumeration will never be garbage collected,
--   so use with care in programs that run for extended periods of time and
--   contains many (especially non-regular) types.
--   
--   Once a type has an instance, it can be enumerated in several ways (by
--   instantiating <a>global</a> to different types). For instance
--   <tt>global :: Count [Maybe Bool]</tt> would only count the number of
--   lists of Maybe Bool of each size (using
--   <a>Control.Enumerable.Count</a>). @global :: Values [Maybe Bool] would
--   give the actual values for all sizes as lists. See <a>FEAT</a> for a
--   more elaborate enumeration type that allows access to any value in the
--   enumeration (given an index) in polynomial time, uniform selection
--   from a given size etc.
--   
--   Instances can be constructed in three ways:
--   
--   1: Manually by passing <a>datatype</a> a list where each element is an
--   application of the constructor functions <a>c0</a>, <a>c1</a> etc, so
--   a data type like Maybe would have <tt>enumerate = datatype [c0
--   Nothing, c1 Just]</tt>. This assumes all field types of all
--   constructors are enumerable (recursive constructors work fine). The
--   functions passed to <tt>cX</tt> do not have to be constructors, but
--   should be injective functions (if they are not injective the
--   enumeration will contain duplicates). So "smart constructors" can be
--   used, for instance the <tt>Rational</tt> datatype is defined by an
--   injection from the natural numbers.
--   
--   2: Automatically with Template Haskell (<a>deriveEnumerable</a>). A
--   top level declaration like <tt>deriveEnumerable ''Maybe</tt> would
--   derive an instance for the <tt>Maybe</tt> data type.
--   
--   3: Manually using the operations of a sized functor (see
--   <a>Control.Sized</a>) to build a <tt>Shareable f a</tt> value, then
--   apply <a>share</a> to it. To use other instances of <a>Enumerable</a>
--   use <a>access</a>.
module Control.Enumerable
class Typeable a => Enumerable a
enumerate :: (Enumerable a, Typeable f, Sized f) => Shared f a

-- | Builds an enumeration of a data type from a list of constructors (see
--   c0-c7)
datatype :: (Typeable a, Sized f, Typeable f) => [Shareable f a] -> Shared f a

-- | Takes a constructor with arity 0 (a pure value)
c0 :: Sized f => a -> Shareable f a

-- | Takes a constructor of arity 1
c1 :: (Enumerable a, Sized f, Typeable f) => (a -> x) -> Shareable f x
c2 :: (Enumerable a, Enumerable b, Sized f, Typeable f) => (a -> b -> x) -> Shareable f x
c3 :: (Enumerable a, Enumerable b, Enumerable c, Sized f, Typeable f) => (a -> b -> c -> x) -> Shareable f x
c4 :: (Enumerable a, Enumerable b, Enumerable c, Enumerable d, Sized f, Typeable f) => (a -> b -> c -> d -> x) -> Shareable f x
c5 :: (Enumerable a, Enumerable b, Enumerable c, Enumerable d, Enumerable e, Sized f, Typeable f) => (a -> b -> c -> d -> e -> x) -> Shareable f x
c6 :: (Enumerable a, Enumerable b, Enumerable c, Enumerable d, Enumerable e, Enumerable g, Sized f, Typeable f) => (a -> b -> c -> d -> e -> g -> x) -> Shareable f x
c7 :: (Enumerable a, Enumerable b, Enumerable c, Enumerable d, Enumerable e, Enumerable g, Enumerable h, Sized f, Typeable f) => (a -> b -> c -> d -> e -> g -> h -> x) -> Shareable f x

-- | This is the primary way to access enumerations for usage. Guarantees
--   global sharing of enumerations of the same type. Note that this means
--   the enumerations are never garbage collected.
global :: (Typeable f, Sized f, Enumerable a) => f a

-- | Guarantees local sharing. All enumerations are shared inside each
--   invokation of local, but may not be shared between them.
local :: (Typeable f, Sized f, Enumerable a) => f a
deriveEnumerable :: Name -> Q [Dec]
dAll :: Name -> ConstructorDeriv
dExcluding :: Name -> ConstructorDeriv -> ConstructorDeriv
dExcept :: Name -> ExpQ -> ConstructorDeriv -> ConstructorDeriv
type ConstructorDeriv = (Name, [(Name, ExpQ)])

-- | Derive an instance of Enumberable with Template Haskell, with rules
--   for some specific constructors
deriveEnumerable' :: ConstructorDeriv -> Q [Dec]

-- | Used instead of enumerate when manually building instances.
access :: (Enumerable a, Sized f, Typeable f) => Shareable f a

-- | Share/memoize a class member of type <tt>f a</tt>.
share :: forall a (f :: Type -> Type). (Typeable a, Typeable f) => Shareable f a -> Shared f a
data Shared (f :: Type -> Type) a
data Shareable (f :: Type -> Type) a

-- | The class <a>Typeable</a> allows a concrete representation of a type
--   to be calculated.
class Typeable (a :: k)

-- | Builds a suitable definition for <tt>coEnumerate</tt> given an pattern
--   matching function for a data type (see source for examples).
function :: (Typeable a, Enumerable b, Sized f, Typeable f) => Shareable f (a -> b) -> Shared f (a -> b)

-- | Work in progress
class Typeable a => CoEnumerable a
coEnumerate :: (CoEnumerable a, Enumerable b, Sized f, Typeable f) => Shared f (a -> b)

-- | A class of infinite precision integral types. <a>Integer</a> is the
--   principal class member.
class (Typeable a, Integral a) => Infinite a
instance (Control.Enumerable.CoEnumerable a, Control.Enumerable.Enumerable b) => Control.Enumerable.Enumerable (a -> b)
instance Control.Enumerable.CoEnumerable GHC.Types.Bool
instance Control.Enumerable.CoEnumerable a => Control.Enumerable.CoEnumerable [a]
instance Control.Enumerable.Infinite GHC.Integer.Type.Integer
instance Control.Enumerable.Infinite a => Control.Enumerable.Enumerable (GHC.Real.Ratio a)
instance Control.Enumerable.Infinite integer => Control.Enumerable.Enumerable (Data.Modifiers.Nat integer)
instance Control.Enumerable.Enumerable ()
instance (Control.Enumerable.Enumerable a, Control.Enumerable.Enumerable b) => Control.Enumerable.Enumerable (a, b)
instance (Control.Enumerable.Enumerable a, Control.Enumerable.Enumerable b, Control.Enumerable.Enumerable c) => Control.Enumerable.Enumerable (a, b, c)
instance (Control.Enumerable.Enumerable a, Control.Enumerable.Enumerable b, Control.Enumerable.Enumerable c, Control.Enumerable.Enumerable d) => Control.Enumerable.Enumerable (a, b, c, d)
instance (Control.Enumerable.Enumerable a, Control.Enumerable.Enumerable b, Control.Enumerable.Enumerable c, Control.Enumerable.Enumerable d, Control.Enumerable.Enumerable e) => Control.Enumerable.Enumerable (a, b, c, d, e)
instance Control.Enumerable.Enumerable GHC.Types.Bool
instance (Control.Enumerable.Enumerable a, Control.Enumerable.Enumerable b) => Control.Enumerable.Enumerable (Data.Either.Either a b)
instance Control.Enumerable.Enumerable a => Control.Enumerable.Enumerable [a]
instance Control.Enumerable.Enumerable a => Control.Enumerable.Enumerable (GHC.Maybe.Maybe a)
instance Control.Enumerable.Enumerable GHC.Types.Ordering
instance Control.Enumerable.Enumerable GHC.Integer.Type.Integer
instance Control.Enumerable.Enumerable GHC.Types.Word
instance Control.Enumerable.Enumerable GHC.Word.Word8
instance Control.Enumerable.Enumerable GHC.Word.Word16
instance Control.Enumerable.Enumerable GHC.Word.Word32
instance Control.Enumerable.Enumerable GHC.Word.Word64
instance Control.Enumerable.Enumerable GHC.Types.Int
instance Control.Enumerable.Enumerable GHC.Int.Int8
instance Control.Enumerable.Enumerable GHC.Int.Int16
instance Control.Enumerable.Enumerable GHC.Int.Int32
instance Control.Enumerable.Enumerable GHC.Int.Int64
instance Control.Enumerable.Enumerable GHC.Types.Char
instance Control.Enumerable.Enumerable GHC.Types.Float
instance Control.Enumerable.Enumerable GHC.Types.Double
instance Control.Enumerable.Enumerable Data.Modifiers.Unicode
instance Control.Enumerable.Enumerable Data.Modifiers.Printable
instance Control.Enumerable.Enumerable a => Control.Enumerable.Enumerable (Data.Modifiers.NonEmpty a)
instance (Data.Typeable.Internal.Typeable f, Control.Sized.Sized f) => Control.Sized.Sized (Data.ClassSharing.Shareable f)

module Control.Enumerable.Values

-- | Constructs all values of a given size.
values :: Enumerable a => Int -> [a]

-- | Constructs all values up to a given size.
values' :: Enumerable a => Int -> [[a]]
allValues :: Enumerable a => [[a]]
newtype Values a
Values :: (Int -> [a]) -> Values a
[runValues] :: Values a -> Int -> [a]
instance GHC.Show.Show (Control.Enumerable.Values.MaxSize a)
instance GHC.Base.Functor Control.Enumerable.Values.MaxSize
instance GHC.Base.Applicative Control.Enumerable.Values.MaxSize
instance GHC.Base.Alternative Control.Enumerable.Values.MaxSize
instance Control.Sized.Sized Control.Enumerable.Values.MaxSize
instance GHC.Base.Functor Control.Enumerable.Values.Values
instance GHC.Base.Applicative Control.Enumerable.Values.Values
instance GHC.Base.Alternative Control.Enumerable.Values.Values
instance Control.Sized.Sized Control.Enumerable.Values.Values

module Control.Enumerable.Count

-- | Counts the number of values of a all sizes. Usage: @global :: Count
--   [Bool]
newtype Count a
Count :: [Integer] -> Count a
[count] :: Count a -> [Integer]

-- | Counts the number of values of a given size, 0 if out of bounds.
(!!*) :: Count a -> Int -> Integer
(</>) :: Count a -> Count a -> Count a
infixl 4 </>
instance GHC.Show.Show (Control.Enumerable.Count.Count a)
instance GHC.Base.Functor Control.Enumerable.Count.Count
instance GHC.Base.Applicative Control.Enumerable.Count.Count
instance GHC.Base.Alternative Control.Enumerable.Count.Count
instance GHC.Base.Semigroup (Control.Enumerable.Count.Count a)
instance GHC.Base.Monoid (Control.Enumerable.Count.Count a)
instance Control.Sized.Sized Control.Enumerable.Count.Count