-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Generic random generators
--
-- Please see the README.
@package generic-random
@version 0.3.0.0
module Generic.Random.Internal.Generic
-- | Pick a constructor with uniform probability, and fill its fields
-- recursively.
--
-- An equivalent definition for Tree is:
--
--
-- genericArbitrary :: Arbitrary a => Gen (Tree a)
-- genericArbitrary =
-- oneof
-- [ Leaf <$> arbitrary -- Uses Arbitrary a
-- , Node <$> arbitrary <*> arbitrary -- Uses Arbitrary (Tree a)
-- ]
--
--
-- Note that for many types, genericArbitrary tends to produce big
-- values. For instance for Tree a values are finite but the
-- average number of Leaf and Node constructors is
-- infinite.
genericArbitrary :: forall a. (Generic a, GA Unsized (Rep a)) => Gen a
-- | This allows to specify the probability distribution of constructors as
-- a list of weights, in the same order as the data type definition.
--
-- An equivalent definition for Tree is:
--
--
-- genericArbitraryFrequency :: Arbitrary a => [Int] -> Gen (Tree a)
-- genericArbitraryFrequency [x, y] =
-- frequency
-- [ (x, Leaf <$> arbitrary)
-- , (y, Node <$> arbitrary <*> arbitrary)
-- ]
--
genericArbitraryFrequency :: forall a. (Generic a, GA Unsized (Rep a)) => [Int] -> Gen a
-- | The size parameter of Gen is divided among the fields of the
-- chosen constructor. When it reaches zero, the generator selects a
-- finite term whenever it can find any of the given type.
--
-- The natural number n determines the maximum depth of
-- terms that can be used to end recursion. It is encoded using
-- Z :: Z and S :: n -> S
-- n.
--
--
-- genericArbitraryFrequency' n weights
--
--
-- With n = Z, the generator looks for a simple nullary
-- constructor. If none exist at the current type, as is the case for our
-- Tree type, it carries on as in
-- genericArbitraryFrequency.
--
--
-- genericArbitraryFrequency' Z :: Arbitrary a => [Int] -> Gen (Tree a)
-- genericArbitraryFrequency' Z [x, y] =
-- frequency
-- [ (x, Leaf <$> arbitrary)
-- , (y, scale (`div` 2) $ Node <$> arbitrary <*> arbitrary)
-- ]
-- -- 2 because Node is 2-ary.
--
--
-- Here is another example:
--
--
-- data Tree' = Leaf1 | Leaf2 | Node3 Tree' Tree' Tree'
-- deriving Generic
--
-- instance Arbitrary Tree' where
-- arbitrary = genericArbitraryFrequency' Z [1, 2, 3]
--
--
-- genericArbitraryFrequency' is equivalent to:
--
--
-- genericArbitraryFrequency' Z :: [Int] -> Gen Tree'
-- genericArbitraryFrequency' Z [x, y, z] =
-- sized $ \n ->
-- if n == 0 then
-- -- If the size parameter is zero, the non-nullary alternative is discarded.
-- frequency $
-- [ (x, return Leaf1)
-- , (y, return Leaf2)
-- ]
-- else
-- frequency $
-- [ (x, return Leaf1)
-- , (y, return Leaf2)
-- , (z, resize (n `div` 3) node)
-- ]
-- -- 3 because Node3 is 3-ary
-- where
-- node = Node3 <$> arbitrary <*> arbitrary <*> arbitrary
--
--
-- To increase the chances of termination when no nullary constructor is
-- directly available, such as in Tree, we can pass a larger
-- depth n. The effectiveness of this parameter depends on the
-- concrete type the generator is used for.
--
-- For instance, if we want to generate a value of type Tree (),
-- there is a value of depth 1 (represented by S
-- Z) that we can use to end recursion: Leaf ().
--
--
-- genericArbitraryFrequency' (S Z) :: [Int] -> Gen (Tree ())
-- genericArbitraryFrequency' (S Z) [x, y] =
-- sized $ \n ->
-- if n == 0 then
-- return (Leaf ())
-- else
-- frequency
-- [ (x, Leaf <$> arbitrary)
-- , (y, scale (`div` 2) $ Node <$> arbitrary <*> arbitrary)
-- ]
--
--
-- Because the argument of Tree must be inspected in order to
-- discover values of type Tree (), we incur some extra
-- constraints if we want polymorphism.
--
-- FlexibleContexts and UndecidableInstances are also
-- required.
--
--
-- instance (Arbitrary a, Generic a, BaseCases Z (Rep a))
-- => Arbitrary (Tree a) where
-- arbitrary = genericArbitraryFrequency' (S Z) [1, 2]
--
--
-- A synonym is provided for brevity.
--
--
-- instance (Arbitrary a, BaseCases' Z a) => Arbitrary (Tree a) where
-- arbitrary = genericArbitraryFrequency' (S Z) [1, 2]
--
genericArbitraryFrequency' :: forall n a. (Generic a, GA (Sized n) (Rep a)) => n -> [Int] -> Gen a
-- | Like genericArbitraryFrequency', but with uniformly distributed
-- constructors.
genericArbitrary' :: forall n a. (Generic a, GA (Sized n) (Rep a)) => n -> Gen a
newtype Freq sized a
Freq :: ([Int] -> Gen a) -> Freq sized a
[unFreq] :: Freq sized a -> [Int] -> Gen a
newtype Gen' sized a
Gen' :: Gen a -> Gen' sized a
[unGen'] :: Gen' sized a -> Gen a
data Sized n
data Unsized
liftGen :: Gen a -> Freq sized a
-- | Generic Arbitrary
class GA sized f
ga :: GA sized f => Freq sized (f p)
gArbitrarySingle :: forall sized f p. GA sized f => Gen' sized (f p)
class GASum sized f
gaSum :: GASum sized f => [Gen' sized (f p)]
class GAProduct f
gaProduct :: GAProduct f => (Int, Gen' Unsized (f p))
newtype Tagged a b
Tagged :: b -> Tagged a b
[unTagged] :: Tagged a b -> b
-- | Zero
data Z
Z :: Z
-- | Successor
data S n
S :: n -> S n
-- | A BaseCases n (Rep a) constraint basically provides
-- the list of values of type a with depth at most n.
class BaseCases n f
baseCases :: BaseCases n f => Tagged n [[f p]]
-- | For convenience.
type BaseCases' n a = (Generic a, BaseCases n (Rep a))
baseCases' :: forall n f p. BaseCases n f => Tagged n [f p]
instance GHC.Base.Applicative (Generic.Random.Internal.Generic.Gen' sized)
instance GHC.Base.Functor (Generic.Random.Internal.Generic.Gen' sized)
instance GHC.Base.Functor (Generic.Random.Internal.Generic.Freq sized)
instance GHC.Base.Applicative (Generic.Random.Internal.Generic.Freq sized)
instance Generic.Random.Internal.Generic.GA sized GHC.Generics.U1
instance Test.QuickCheck.Arbitrary.Arbitrary c => Generic.Random.Internal.Generic.GA sized (GHC.Generics.K1 i c)
instance Generic.Random.Internal.Generic.GA sized f => Generic.Random.Internal.Generic.GA sized (GHC.Generics.M1 i c f)
instance (Generic.Random.Internal.Generic.GASum (Generic.Random.Internal.Generic.Sized n) f, Generic.Random.Internal.Generic.GASum (Generic.Random.Internal.Generic.Sized n) g, Generic.Random.Internal.Generic.BaseCases n f, Generic.Random.Internal.Generic.BaseCases n g) => Generic.Random.Internal.Generic.GA (Generic.Random.Internal.Generic.Sized n) (f GHC.Generics.:+: g)
instance (Generic.Random.Internal.Generic.GASum Generic.Random.Internal.Generic.Unsized f, Generic.Random.Internal.Generic.GASum Generic.Random.Internal.Generic.Unsized g) => Generic.Random.Internal.Generic.GA Generic.Random.Internal.Generic.Unsized (f GHC.Generics.:+: g)
instance (Generic.Random.Internal.Generic.GA Generic.Random.Internal.Generic.Unsized f, Generic.Random.Internal.Generic.GA Generic.Random.Internal.Generic.Unsized g) => Generic.Random.Internal.Generic.GA Generic.Random.Internal.Generic.Unsized (f GHC.Generics.:*: g)
instance (Generic.Random.Internal.Generic.GAProduct f, Generic.Random.Internal.Generic.GAProduct g) => Generic.Random.Internal.Generic.GA (Generic.Random.Internal.Generic.Sized n) (f GHC.Generics.:*: g)
instance (Generic.Random.Internal.Generic.GASum sized f, Generic.Random.Internal.Generic.GASum sized g) => Generic.Random.Internal.Generic.GASum sized (f GHC.Generics.:+: g)
instance Generic.Random.Internal.Generic.GA sized f => Generic.Random.Internal.Generic.GASum sized (GHC.Generics.M1 i c f)
instance Generic.Random.Internal.Generic.GA Generic.Random.Internal.Generic.Unsized f => Generic.Random.Internal.Generic.GAProduct (GHC.Generics.M1 i c f)
instance (Generic.Random.Internal.Generic.GAProduct f, Generic.Random.Internal.Generic.GAProduct g) => Generic.Random.Internal.Generic.GAProduct (f GHC.Generics.:*: g)
instance Generic.Random.Internal.Generic.BaseCases n GHC.Generics.U1
instance Generic.Random.Internal.Generic.BaseCases n f => Generic.Random.Internal.Generic.BaseCases n (GHC.Generics.M1 i c f)
instance Generic.Random.Internal.Generic.BaseCases Generic.Random.Internal.Generic.Z (GHC.Generics.K1 i c)
instance (GHC.Generics.Generic c, Generic.Random.Internal.Generic.BaseCases n (GHC.Generics.Rep c)) => Generic.Random.Internal.Generic.BaseCases (Generic.Random.Internal.Generic.S n) (GHC.Generics.K1 i c)
instance (Generic.Random.Internal.Generic.BaseCases n f, Generic.Random.Internal.Generic.BaseCases n g) => Generic.Random.Internal.Generic.BaseCases n (f GHC.Generics.:+: g)
instance (Generic.Random.Internal.Generic.BaseCases n f, Generic.Random.Internal.Generic.BaseCases n g) => Generic.Random.Internal.Generic.BaseCases n (f GHC.Generics.:*: g)
-- | Simple Generics-based arbitrary generators.
--
-- Here is an example. Define your type.
--
--
-- data Tree a = Leaf a | Node (Tree a) (Tree a)
-- deriving Generic
--
--
-- Pick an arbitrary implementation.
--
--
-- instance Arbitrary a => Arbitrary (Tree a) where
-- arbitrary = genericArbitraryFrequency [9, 8]
--
--
-- arbitrary :: Gen (Tree a) picks a Leaf with
-- probability 9/17, or a Node with probability 8/17, and
-- recursively fills their fields with arbitrary.
module Generic.Random.Generic
-- | Pick a constructor with uniform probability, and fill its fields
-- recursively.
--
-- An equivalent definition for Tree is:
--
--
-- genericArbitrary :: Arbitrary a => Gen (Tree a)
-- genericArbitrary =
-- oneof
-- [ Leaf <$> arbitrary -- Uses Arbitrary a
-- , Node <$> arbitrary <*> arbitrary -- Uses Arbitrary (Tree a)
-- ]
--
--
-- Note that for many types, genericArbitrary tends to produce big
-- values. For instance for Tree a values are finite but the
-- average number of Leaf and Node constructors is
-- infinite.
genericArbitrary :: forall a. (Generic a, GA Unsized (Rep a)) => Gen a
-- | This allows to specify the probability distribution of constructors as
-- a list of weights, in the same order as the data type definition.
--
-- An equivalent definition for Tree is:
--
--
-- genericArbitraryFrequency :: Arbitrary a => [Int] -> Gen (Tree a)
-- genericArbitraryFrequency [x, y] =
-- frequency
-- [ (x, Leaf <$> arbitrary)
-- , (y, Node <$> arbitrary <*> arbitrary)
-- ]
--
genericArbitraryFrequency :: forall a. (Generic a, GA Unsized (Rep a)) => [Int] -> Gen a
-- | The size parameter of Gen is divided among the fields of the
-- chosen constructor. When it reaches zero, the generator selects a
-- finite term whenever it can find any of the given type.
--
-- The natural number n determines the maximum depth of
-- terms that can be used to end recursion. It is encoded using
-- Z :: Z and S :: n -> S
-- n.
--
--
-- genericArbitraryFrequency' n weights
--
--
-- With n = Z, the generator looks for a simple nullary
-- constructor. If none exist at the current type, as is the case for our
-- Tree type, it carries on as in
-- genericArbitraryFrequency.
--
--
-- genericArbitraryFrequency' Z :: Arbitrary a => [Int] -> Gen (Tree a)
-- genericArbitraryFrequency' Z [x, y] =
-- frequency
-- [ (x, Leaf <$> arbitrary)
-- , (y, scale (`div` 2) $ Node <$> arbitrary <*> arbitrary)
-- ]
-- -- 2 because Node is 2-ary.
--
--
-- Here is another example:
--
--
-- data Tree' = Leaf1 | Leaf2 | Node3 Tree' Tree' Tree'
-- deriving Generic
--
-- instance Arbitrary Tree' where
-- arbitrary = genericArbitraryFrequency' Z [1, 2, 3]
--
--
-- genericArbitraryFrequency' is equivalent to:
--
--
-- genericArbitraryFrequency' Z :: [Int] -> Gen Tree'
-- genericArbitraryFrequency' Z [x, y, z] =
-- sized $ \n ->
-- if n == 0 then
-- -- If the size parameter is zero, the non-nullary alternative is discarded.
-- frequency $
-- [ (x, return Leaf1)
-- , (y, return Leaf2)
-- ]
-- else
-- frequency $
-- [ (x, return Leaf1)
-- , (y, return Leaf2)
-- , (z, resize (n `div` 3) node)
-- ]
-- -- 3 because Node3 is 3-ary
-- where
-- node = Node3 <$> arbitrary <*> arbitrary <*> arbitrary
--
--
-- To increase the chances of termination when no nullary constructor is
-- directly available, such as in Tree, we can pass a larger
-- depth n. The effectiveness of this parameter depends on the
-- concrete type the generator is used for.
--
-- For instance, if we want to generate a value of type Tree (),
-- there is a value of depth 1 (represented by S
-- Z) that we can use to end recursion: Leaf ().
--
--
-- genericArbitraryFrequency' (S Z) :: [Int] -> Gen (Tree ())
-- genericArbitraryFrequency' (S Z) [x, y] =
-- sized $ \n ->
-- if n == 0 then
-- return (Leaf ())
-- else
-- frequency
-- [ (x, Leaf <$> arbitrary)
-- , (y, scale (`div` 2) $ Node <$> arbitrary <*> arbitrary)
-- ]
--
--
-- Because the argument of Tree must be inspected in order to
-- discover values of type Tree (), we incur some extra
-- constraints if we want polymorphism.
--
-- FlexibleContexts and UndecidableInstances are also
-- required.
--
--
-- instance (Arbitrary a, Generic a, BaseCases Z (Rep a))
-- => Arbitrary (Tree a) where
-- arbitrary = genericArbitraryFrequency' (S Z) [1, 2]
--
--
-- A synonym is provided for brevity.
--
--
-- instance (Arbitrary a, BaseCases' Z a) => Arbitrary (Tree a) where
-- arbitrary = genericArbitraryFrequency' (S Z) [1, 2]
--
genericArbitraryFrequency' :: forall n a. (Generic a, GA (Sized n) (Rep a)) => n -> [Int] -> Gen a
-- | Like genericArbitraryFrequency', but with uniformly distributed
-- constructors.
genericArbitrary' :: forall n a. (Generic a, GA (Sized n) (Rep a)) => n -> Gen a
-- | Zero
data Z
Z :: Z
-- | Successor
data S n
S :: n -> S n
-- | For convenience.
type BaseCases' n a = (Generic a, BaseCases n (Rep a))
-- | A BaseCases n (Rep a) constraint basically provides
-- the list of values of type a with depth at most n.
class BaseCases n f
module Generic.Random.Internal.Types
data SomeData m
[SomeData] :: Data a => m a -> SomeData m
type SomeData' = SomeData Proxy
-- | Dummy instance for debugging.
data Alias m
[Alias] :: (Data a, Data b) => !(m a -> m b) -> Alias m
type AliasR m = Alias (RejectT m)
-- | Dummy instance for debugging.
-- | Main constructor for Alias.
alias :: (Monad m, Data a, Data b) => (a -> m b) -> Alias m
-- | Main constructor for AliasR.
aliasR :: (Monad m, Data a, Data b) => (a -> m b) -> AliasR m
-- |
-- coerceAlias :: Alias m -> Alias (AMonadRandom m)
--
coerceAlias :: Coercible m n => Alias m -> Alias n
-- |
-- coerceAliases :: [Alias m] -> [Alias (AMonadRandom m)]
--
coerceAliases :: Coercible m n => [Alias m] -> [Alias n]
-- |
-- composeCast f g = f . g
--
composeCastM :: forall a b c d m. (Typeable b, Typeable c) => (m c -> d) -> (a -> m b) -> (a -> d)
castM :: forall a b m. (Typeable a, Typeable b) => m a -> m b
unSomeData :: Typeable a => SomeData m -> m a
applyCast :: (Typeable a, Data b) => (m a -> m b) -> SomeData m -> SomeData m
castError :: (Typeable a, Typeable b) => proxy a -> proxy' b -> c
withProxy :: (a -> b) -> proxy a -> b
reproxy :: proxy a -> Proxy a
proxyType :: m a -> proxy a -> m a
someData' :: Data a => proxy a -> SomeData'
-- | Size as the number of constructors.
type Size = Int
-- | Internal transformer for rejection sampling.
--
--
-- ReaderT Size (StateT Size (MaybeT m)) a
--
newtype RejectT m a
RejectT :: (forall r. Size -> Size -> m r -> (Size -> a -> m r) -> m r) -> RejectT m a
[unRejectT] :: RejectT m a -> forall r. Size -> Size -> m r -> (Size -> a -> m r) -> m r
-- | Set lower bound
runRejectT :: Monad m => (Size, Size) -> RejectT m a -> m a
newtype AMonadRandom m a
AMonadRandom :: m a -> AMonadRandom m a
[asMonadRandom] :: AMonadRandom m a -> m a
-- | MonadRandomLike m defines basic components to build
-- generators, allowing the implementation to remain abstract over both
-- the Gen type and MonadRandom instances.
--
-- For the latter, the wrapper AMonadRandom is provided to avoid
-- overlapping instances.
class Monad m => MonadRandomLike m where incr = return ()
-- | Called for every constructor. Counter for ceiled rejection sampling.
incr :: MonadRandomLike m => m ()
-- | doubleR upperBound: generates values in [0,
-- upperBound].
doubleR :: MonadRandomLike m => Double -> m Double
-- | integerR upperBound: generates values in [0,
-- upperBound-1].
integerR :: MonadRandomLike m => Integer -> m Integer
-- | Default Int generator.
int :: MonadRandomLike m => m Int
-- | Default Double generator.
double :: MonadRandomLike m => m Double
-- | Default Char generator.
char :: MonadRandomLike m => m Char
instance GHC.Base.Monad m => GHC.Base.Monad (Generic.Random.Internal.Types.AMonadRandom m)
instance GHC.Base.Applicative m => GHC.Base.Applicative (Generic.Random.Internal.Types.AMonadRandom m)
instance GHC.Base.Functor m => GHC.Base.Functor (Generic.Random.Internal.Types.AMonadRandom m)
instance GHC.Show.Show (Generic.Random.Internal.Types.SomeData m)
instance GHC.Show.Show (Generic.Random.Internal.Types.Alias m)
instance GHC.Base.Functor (Generic.Random.Internal.Types.RejectT m)
instance GHC.Base.Applicative (Generic.Random.Internal.Types.RejectT m)
instance GHC.Base.Monad (Generic.Random.Internal.Types.RejectT m)
instance Control.Monad.Trans.Class.MonadTrans Generic.Random.Internal.Types.RejectT
instance Control.Monad.Trans.Class.MonadTrans Generic.Random.Internal.Types.AMonadRandom
instance Generic.Random.Internal.Types.MonadRandomLike Test.QuickCheck.Gen.Gen
instance Generic.Random.Internal.Types.MonadRandomLike m => Generic.Random.Internal.Types.MonadRandomLike (Generic.Random.Internal.Types.RejectT m)
instance Control.Monad.Random.Class.MonadRandom m => Generic.Random.Internal.Types.MonadRandomLike (Generic.Random.Internal.Types.AMonadRandom m)
-- | Solve systems of equations
module Generic.Random.Internal.Solver
data SolveArgs
SolveArgs :: Double -> Int -> SolveArgs
[accuracy] :: SolveArgs -> Double
[numIterations] :: SolveArgs -> Int
defSolveArgs :: SolveArgs
findZero :: SolveArgs -> (forall s. Vector (AD s (Forward R)) -> Vector (AD s (Forward R))) -> Vector R -> Maybe (Vector R)
fixedPoint :: SolveArgs -> (forall a. (Mode a, Scalar a ~ R) => Vector a -> Vector a) -> Vector R -> Maybe (Vector R)
-- | Assuming p . f is satisfied only for positive values in some
-- interval (0, r], find f r.
search :: (Double -> a) -> (a -> Bool) -> (Double, a)
instance GHC.Show.Show Generic.Random.Internal.Solver.SolveArgs
instance GHC.Classes.Ord Generic.Random.Internal.Solver.SolveArgs
instance GHC.Classes.Eq Generic.Random.Internal.Solver.SolveArgs
-- | General helper functions
module Generic.Random.Internal.Common
frequencyWith :: (Ord r, Num r, Monad m) => (r -> m r) -> [(r, m a)] -> m a
-- | partitions k n: lists of non-negative integers of length
-- n with sum less than or equal to k.
partitions :: Int -> Int -> [[Int]]
-- | Binomial coefficient.
--
--
-- binomial n k == factorial n `div` (factorial k * factorial (n-k))
--
binomial :: Int -> Int -> Integer
-- | Multinomial coefficient.
--
--
-- multinomial n ps == factorial n `div` product [factorial p | p <- ps]
--
multinomial :: Int -> [Int] -> Integer
module Generic.Random.Internal.Oracle
-- | We build a dictionary which reifies type information in order to
-- create a Boltzmann generator.
--
-- We denote by n (or count) the number of types in the
-- dictionary.
--
-- Every type has an index 0 <= i < n; the variable X
-- i represents its generating function C_i(x), and X
-- (i + k*n) the GF of its k-th "pointing"
-- C_i[k](x); we have
--
--
-- C_i[0](x) = C_i(x)
-- C_i[k+1](x) = x * C_i[k]'(x)
--
--
-- where C_i[k]' is the derivative of C_i[k]. See also
-- point.
--
-- The order (or valuation) of a power series is the index
-- of the first non-zero coefficient, called the leading
-- coefficient.
data DataDef m
DataDef :: Int -> Int -> HashMap TypeRep (Either Aliased Ix) -> HashMap Ix SomeData' -> HashMap Aliased (Ix, Alias m) -> HashMap C [(Integer, Constr, [C'])] -> HashMap Ix (Nat, Integer) -> HashMap Ix Int -> DataDef m
-- | Number of registered types
[count] :: DataDef m -> Int
-- | Number of iterations of the pointing operator
[points] :: DataDef m -> Int
-- | Map from types to indices
[index] :: DataDef m -> HashMap TypeRep (Either Aliased Ix)
-- | Inverse map from indices to types
[xedni] :: DataDef m -> HashMap Ix SomeData'
-- | Inverse map to aliases
[xedni'] :: DataDef m -> HashMap Aliased (Ix, Alias m)
-- | Structure of types and their pointings (up to points, initially
-- 0)
--
-- Primitive types and empty types are mapped to an empty constructor
-- list, and can be distinguished using dataTypeRep on the
-- SomeData associated to it by xedni.
--
-- The integer is a multiplicity which can be > 1 for pointings.
[types] :: DataDef m -> HashMap C [(Integer, Constr, [C'])]
-- | Leading term a * x ^ u of the generating functions
-- C_i[k](x) in the form (u, a).
--
--
-- - Order u Smallest size of objects of a given
-- type.
-- - Leading coefficient a number of objects of
-- smallest size.
--
[lTerm] :: DataDef m -> HashMap Ix (Nat, Integer)
-- | Degrees of the generating functions, when applicable: greatest size of
-- objects of a given type.
[degree] :: DataDef m -> HashMap Ix Int
-- | A pair C i k represents the k-th "pointing" of the
-- type at index i, with generating function C_i[k](x).
data C
C :: Ix -> Int -> C
data AC
AC :: Aliased -> Int -> AC
type C' = (Maybe Aliased, C)
newtype Aliased
Aliased :: Int -> Aliased
type Ix = Int
data Nat
Zero :: Nat
Succ :: Nat -> Nat
natToInt :: Nat -> Int
infinity :: Nat
dataDef :: [Alias m] -> DataDef m
-- | Find all types that may be types of subterms of a value of type
-- a.
--
-- This will loop if there are infinitely many such types.
collectTypes :: Data a => [Alias m] -> proxy a -> DataDef m
-- | Primitive datatypes have C(x) = x: they are considered as
-- having a single object (lCoef) of size 1 (order)).
primOrder :: Int
primOrder' :: Nat
primlCoef :: Integer
-- | The type of the first argument of gunfold.
type GUnfold m = forall b r. Data b => m (b -> r) -> m r
-- | Type of xedni'.
type AMap m = HashMap Aliased (Ix, Alias m)
collectTypesM :: Data a => proxy a -> State (DataDef m) (Either Aliased Ix, ((Nat, Integer), Maybe Int))
chaseType :: Data a => proxy a -> ((Maybe (Alias m), Ix) -> AMap m -> AMap m) -> State (DataDef m) (Either Aliased Ix, ((Nat, Integer), Maybe Int))
-- | Traversal of the definition of a datatype.
traverseType :: Data a => proxy a -> Ix -> State (DataDef m) (Either Aliased Ix, ((Nat, Integer), Maybe Int))
traverseType' :: Data a => proxy a -> DataType -> State (DataDef m) ([(Integer, Constr, [(Maybe Aliased, C)])], ((Nat, Integer), Maybe Int))
-- | If (u, a) represents a power series of leading term a * x
-- ^ u, and similarly for (u', a'), this finds the leading
-- term of their sum.
--
-- The comparison of Nat is unrolled here for maximum laziness.
lPlus :: (Nat, Integer) -> (Nat, Integer) -> (Nat, Integer)
-- | Sum of a list of series.
lSum :: [(Nat, Integer)] -> (Nat, Integer)
-- | Leading term of a product of series.
lMul :: (Nat, Integer) -> (Nat, Integer) -> (Nat, Integer)
lProd :: [(Nat, Integer)] -> (Nat, Integer)
maxDegree :: [Maybe Int] -> Maybe Int
-- | Pointing operator.
--
-- Populates a DataDef with one more level of pointings.
-- (collectTypes produces a dictionary at level 0.)
--
-- The "pointing" of a type t is a derived type whose values are
-- essentially values of type t, with one of their constructors
-- being "pointed". Alternatively, we may turn every constructor into
-- variants that indicate the position of points.
--
--
-- -- Original type
-- data Tree = Node Tree Tree | Leaf
-- -- Pointing of Tree
-- data Tree'
-- = Tree' Tree -- Point at the root
-- | Node'0 Tree' Tree -- Point to the left
-- | Node'1 Tree Tree' -- Point to the right
-- -- Pointing of the pointing
-- -- Notice that the "points" introduced by both applications of pointing
-- -- are considered different: exchanging their positions (when different)
-- -- produces a different tree.
-- data Tree''
-- = Tree'' Tree' -- Point 2 at the root, the inner Tree' places point 1
-- | Node'0' Tree' Tree -- Point 1 at the root, point 2 to the left
-- | Node'1' Tree Tree' -- Point 1 at the root, point 2 to the right
-- | Node'0'0 Tree'' Tree -- Points 1 and 2 to the left
-- | Node'0'1 Tree' Tree' -- Point 1 to the left, point 2 to the right
-- | Node'1'0 Tree' Tree' -- Point 1 to the right, point 2 to the left
-- | Node'0'1 Tree Tree'' -- Points 1 and 2 to the right
--
--
-- If we ignore points, some constructors are equivalent. Thus we may
-- simply calculate their multiplicity instead of duplicating them.
--
-- Given a constructor with c arguments C x_1 ... x_c,
-- and a sequence p_0 + p_1 + ... + p_c = k corresponding to a
-- distribution of k points (p_0 are assigned to the
-- constructor C itself, and for i > 0, p_i
-- points are assigned within the i-th subterm), the
-- multiplicity of the constructor paired with that distribution is the
-- multinomial coefficient multinomial k [p_1, ..., p_c].
point :: DataDef m -> DataDef m
-- | An oracle gives the values of the generating functions at some
-- x.
type Oracle = HashMap C Double
-- | Find the value of x such that the average size of the
-- generator for the k-1-th pointing is equal to size,
-- and produce the associated oracle. If the size is Nothing,
-- find the radius of convergence.
--
-- The search evaluates the generating functions for some values of
-- x in order to run a binary search. The evaluator is
-- implemented using Newton's method, the convergence of which has been
-- shown for relevant systems in Boltzmann Oracle for Combinatorial
-- Systems, C. Pivoteau, B. Salvy, M. Soria.
makeOracle :: DataDef m -> TypeRep -> Maybe Double -> Oracle
-- | Generating function definition. This defines a Phi_i[k]
-- function associated with the k-th pointing of the type at
-- index i, such that:
--
--
-- C_i[k](x)
-- = Phi_i[k](x, C_0[0](x), ..., C_(n-1)[0](x),
-- ..., C_0[k](x), ..., C_(n-1)[k](x))
--
--
-- Primitive datatypes have C(x) = x: they are considered as
-- having a single object (lCoef) of size 1 (order)).
phi :: Num a => DataDef m -> C -> [(Integer, constr, [C'])] -> a -> Vector a -> a
-- | Maps a key representing a type a (or one of its pointings) to
-- a generator m a.
type Generators m = (HashMap AC (SomeData m), HashMap C (SomeData m))
-- | Build all involved generators at once.
makeGenerators :: forall m. MonadRandomLike m => DataDef m -> Oracle -> Generators m
type SmallGenerators m = (HashMap Aliased (SomeData m), HashMap Ix (SomeData m))
-- | Generators of values of minimal sizes.
smallGenerators :: forall m. MonadRandomLike m => DataDef m -> SmallGenerators m
generate :: Applicative m => GUnfold (ReaderT [SomeData m] m)
defGen :: (Data a, MonadRandomLike m) => m a
(?) :: DataDef m -> C -> Int
-- |
-- dd ? (listCs dd !! i) = i
--
listCs :: DataDef m -> [C]
ix :: C -> Int
-- |
-- dd ? (dd ?! i) = i
--
(?!) :: DataDef m -> Int -> C
getGenerator :: Data a => DataDef m -> Generators m -> proxy a -> Int -> m a
getSmallGenerator :: Data a => DataDef m -> SmallGenerators m -> proxy a -> m a
(#!) :: (Eq k, Hashable k) => HashMap k v -> k -> v
instance GHC.Show.Show (Generic.Random.Internal.Oracle.DataDef m)
instance GHC.Show.Show Generic.Random.Internal.Oracle.Nat
instance GHC.Classes.Ord Generic.Random.Internal.Oracle.Nat
instance GHC.Classes.Eq Generic.Random.Internal.Oracle.Nat
instance GHC.Generics.Generic Generic.Random.Internal.Oracle.C
instance GHC.Show.Show Generic.Random.Internal.Oracle.C
instance GHC.Classes.Ord Generic.Random.Internal.Oracle.C
instance GHC.Classes.Eq Generic.Random.Internal.Oracle.C
instance GHC.Generics.Generic Generic.Random.Internal.Oracle.AC
instance GHC.Show.Show Generic.Random.Internal.Oracle.AC
instance GHC.Classes.Ord Generic.Random.Internal.Oracle.AC
instance GHC.Classes.Eq Generic.Random.Internal.Oracle.AC
instance GHC.Generics.Generic Generic.Random.Internal.Oracle.Aliased
instance GHC.Show.Show Generic.Random.Internal.Oracle.Aliased
instance GHC.Classes.Ord Generic.Random.Internal.Oracle.Aliased
instance GHC.Classes.Eq Generic.Random.Internal.Oracle.Aliased
instance Data.Hashable.Class.Hashable Generic.Random.Internal.Oracle.C
instance Data.Hashable.Class.Hashable Generic.Random.Internal.Oracle.AC
instance Data.Hashable.Class.Hashable Generic.Random.Internal.Oracle.Aliased
instance GHC.Base.Monoid Generic.Random.Internal.Oracle.Nat
module Generic.Random.Internal.Data
-- | Sized generator.
data SG r
SG :: Size -> Maybe Size -> (Points -> Maybe Double -> r) -> (Points -> r) -> SG r
[minSize] :: SG r -> Size
[maxSizeM] :: SG r -> Maybe Size
[runSG] :: SG r -> Points -> Maybe Double -> r
[runSmallG] :: SG r -> Points -> r
-- | Number of pointing iterations.
type Points = Int
rangeSG :: SG r -> (Size, Maybe Size)
-- | For documentation.
applySG :: SG r -> Points -> Maybe Double -> r
make :: (Data a, MonadRandomLike m) => [Alias m] -> proxy a -> SG (m a)
makeR :: (Data a, MonadRandomLike m) => [AliasR m] -> proxy a -> SG ((Size, Size) -> m a)
-- | The size of a value is its number of constructors.
--
-- Here, however, the Size' type is interpreted differently to
-- make better use of QuickCheck's size parameter provided by the
-- sized combinator, so that we generate non-trivial data even at
-- very small size values.
--
-- For infinite types, with objects of unbounded sizes >
-- minSize, given a parameter delta :: Size', the
-- produced values have an average size close to minSize +
-- delta.
--
-- For example, values of type Either () [Bool] have at least
-- two constructors, so
--
--
-- generator delta :: Gen (Either () [Bool])
--
--
-- will target sizes close to 2 + delta; the offset becomes less
-- noticeable as delta grows to infinity.
--
-- For finite types with sizes in [minSize, maxSize], the target
-- expected size is obtained by clamping a Size' to [0,
-- 99] and applying an affine mapping.
type Size' = Int
rescale :: SG r -> Size' -> Double
apply :: SG r -> Points -> Maybe Size' -> r
applyR :: SG ((Size, Size) -> r) -> Points -> Maybe Size' -> (Size', Size') -> r
rescaleInterval :: SG r -> (Size', Size') -> (Size, Size)
-- |
-- 'epsilon' = 0.1
--
--
-- Default approximation ratio.
epsilon :: Double
-- |
-- (size * (1 - epsilon), size * (1 + epsilon))
--
tolerance :: Double -> Int -> (Int, Int)
memo :: (t -> [t2] -> SG r) -> (SG r -> t1 -> Maybe Int -> a) -> t -> t1 -> Int -> a
sparseSized :: (Int -> a) -> Maybe Int -> Int -> a
instance GHC.Base.Functor Generic.Random.Internal.Data.SG
-- | Generic Boltzmann samplers.
--
-- Here, the words "sampler" and "generator" are used
-- interchangeably.
--
-- Given an algebraic datatype:
--
--
-- data A = A1 B C | A2 D
--
--
-- a Boltzmann sampler is recursively defined by choosing a constructor
-- with some fixed distribution, and independently generating
-- values for the corresponding fields with the same method.
--
-- A key component is the aforementioned distribution, defined for every
-- type such that the resulting generator produces a finite value in the
-- end. These distributions are obtained from a precomputed object called
-- oracle, which we will not describe further here.
--
-- Oracles depend on the target size of the generated data (except for
-- singular samplers), and can be fairly expensive to compute repeatedly,
-- hence some of the functions below attempt to avoid (re)computing too
-- many of them even when the required size changes.
--
-- When these functions are specialized, oracles are memoized and will be
-- reused for different sizes.
module Generic.Random.Data
-- | The size of a value is its number of constructors.
--
-- Here, however, the Size' type is interpreted differently to
-- make better use of QuickCheck's size parameter provided by the
-- sized combinator, so that we generate non-trivial data even at
-- very small size values.
--
-- For infinite types, with objects of unbounded sizes >
-- minSize, given a parameter delta :: Size', the
-- produced values have an average size close to minSize +
-- delta.
--
-- For example, values of type Either () [Bool] have at least
-- two constructors, so
--
--
-- generator delta :: Gen (Either () [Bool])
--
--
-- will target sizes close to 2 + delta; the offset becomes less
-- noticeable as delta grows to infinity.
--
-- For finite types with sizes in [minSize, maxSize], the target
-- expected size is obtained by clamping a Size' to [0,
-- 99] and applying an affine mapping.
type Size' = Int
-- |
-- generatorSR :: Int -> Gen a
-- asMonadRandom . generatorSR :: MonadRandom m => Int -> m a
--
--
-- Singular ceiled rejection sampler.
generatorSR :: (Data a, MonadRandomLike m) => Size' -> m a
-- |
-- generatorP :: Int -> Gen a
-- asMonadRandom . generatorP :: MonadRandom m => Int -> m a
--
--
-- Generator of pointed values.
generatorP :: (Data a, MonadRandomLike m) => Size' -> m a
-- | Pointed generator with rejection.
generatorPR :: (Data a, MonadRandomLike m) => Size' -> m a
-- | Generator with rejection and dynamic average size.
generatorR :: (Data a, MonadRandomLike m) => Size' -> m a
-- | Pointed generator.
generatorP' :: (Data a, MonadRandomLike m) => Size' -> m a
-- | Pointed generator with rejection.
generatorPR' :: (Data a, MonadRandomLike m) => Size' -> m a
-- | Ceiled rejection sampler with given average size.
generatorR' :: (Data a, MonadRandomLike m) => Size' -> m a
-- | Basic boltzmann sampler with no optimization.
generator' :: (Data a, MonadRandomLike m) => Size' -> m a
generatorSRWith :: (Data a, MonadRandomLike m) => [AliasR m] -> Size' -> m a
generatorPWith :: (Data a, MonadRandomLike m) => [Alias m] -> Size' -> m a
generatorPRWith :: (Data a, MonadRandomLike m) => [AliasR m] -> Size' -> m a
generatorRWith :: (Data a, MonadRandomLike m) => [AliasR m] -> Size' -> m a
generatorPWith' :: (Data a, MonadRandomLike m) => [Alias m] -> Size' -> m a
generatorPRWith' :: (Data a, MonadRandomLike m) => [AliasR m] -> Size' -> m a
generatorRWith' :: (Data a, MonadRandomLike m) => [AliasR m] -> Size' -> m a
generatorWith' :: (Data a, MonadRandomLike m) => [Alias m] -> Size' -> m a
-- | Number of pointing iterations.
type Points = Int
generatorM :: (Data a, MonadRandomLike m) => [Alias m] -> Points -> Size' -> m a
generatorMR :: (Data a, MonadRandomLike m) => [AliasR m] -> Points -> Size' -> (Size', Size') -> m a
-- | Boltzmann sampler without rejection.
generator_ :: (Data a, MonadRandomLike m) => [Alias m] -> Points -> Maybe Size' -> m a
-- | Boltzmann sampler with rejection.
generatorR_ :: (Data a, MonadRandomLike m) => [AliasR m] -> Points -> Maybe Size' -> (Size', Size') -> m a
-- | MonadRandomLike m defines basic components to build
-- generators, allowing the implementation to remain abstract over both
-- the Gen type and MonadRandom instances.
--
-- For the latter, the wrapper AMonadRandom is provided to avoid
-- overlapping instances.
class Monad m => MonadRandomLike m where incr = return ()
-- | Called for every constructor. Counter for ceiled rejection sampling.
incr :: MonadRandomLike m => m ()
-- | doubleR upperBound: generates values in [0,
-- upperBound].
doubleR :: MonadRandomLike m => Double -> m Double
-- | integerR upperBound: generates values in [0,
-- upperBound-1].
integerR :: MonadRandomLike m => Integer -> m Integer
-- | Default Int generator.
int :: MonadRandomLike m => m Int
-- | Default Double generator.
double :: MonadRandomLike m => m Double
-- | Default Char generator.
char :: MonadRandomLike m => m Char
newtype AMonadRandom m a
AMonadRandom :: m a -> AMonadRandom m a
[asMonadRandom] :: AMonadRandom m a -> m a
-- | Main constructor for Alias.
alias :: (Monad m, Data a, Data b) => (a -> m b) -> Alias m
-- | Main constructor for AliasR.
aliasR :: (Monad m, Data a, Data b) => (a -> m b) -> AliasR m
-- |
-- coerceAlias :: Alias m -> Alias (AMonadRandom m)
--
coerceAlias :: Coercible m n => Alias m -> Alias n
-- |
-- coerceAliases :: [Alias m] -> [Alias (AMonadRandom m)]
--
coerceAliases :: Coercible m n => [Alias m] -> [Alias n]
data Alias m
[Alias] :: (Data a, Data b) => !(m a -> m b) -> Alias m
type AliasR m = Alias (RejectT m)
-- | Applicative interface to define recursive structures and derive
-- Boltzmann samplers.
--
-- Given the recursive structure of the types, and how to combine
-- generators, the library takes care of computing the oracles and
-- setting the right distributions.
module Generic.Random.Boltzmann
class Embed f m
emap :: Embed f m => (m a -> m b) -> f a -> f b
-- | A natural transformation between f and m?
embed :: Embed f m => m a -> f a
-- | Applicative defines a product, Alternative defines an
-- addition, with scalar multiplication we get a module.
--
-- This typeclass allows to directly tweak weights in the oracle by
-- chosen factors.
class (Alternative f, Num (Scalar f)) => Module f where type Scalar f :: * scalar x = x <.> pure () x <.> f = scalar x *> f where {
type family Scalar f :: *;
}
-- | Scalar embedding.
scalar :: Module f => Scalar f -> f ()
-- | Scalar multiplication.
(<.>) :: Module f => Scalar f -> f a -> f a
type Endo a = a -> a
data System f a c
System :: Int -> (f () -> Vector (f a) -> (Vector (f a), c)) -> System f a c
[dim] :: System f a c -> Int
[sys'] :: System f a c -> f () -> Vector (f a) -> (Vector (f a), c)
sys :: System f a c -> f () -> Vector (f a) -> Vector (f a)
newtype ConstModule r a
ConstModule :: r -> ConstModule r a
[unConstModule] :: ConstModule r a -> r
solve :: forall b c. (forall a. Num a => System (ConstModule a) b c) -> Double -> Maybe (Vector Double)
sizedGenerator :: forall b c m. MonadRandomLike m => (forall f. (Module f, Embed f m) => System (Pointiful f) b c) -> Int -> Int -> Maybe Double -> m b
solveSized :: forall b c. (forall a. Num a => System (Pointiful (ConstModule a)) b c) -> Int -> Int -> Maybe Double -> (Double, Vector Double)
newtype Weighted m a
Weighted :: [(Double, m a)] -> Weighted m a
weighted :: Double -> m a -> Weighted m a
runWeighted :: MonadRandomLike m => Weighted m a -> (Double, m a)
sfix :: MonadRandomLike m => System (Weighted m) b c -> Double -> Vector Double -> (Vector (m b), c)
data Pointiful f a
Pointiful :: [f a] -> Pointiful f a
Zero :: (f a) -> Pointiful f a
unPointiful :: Alternative f => Pointiful f a -> [f a]
point :: Module f => Int -> System (Pointiful f) b c -> System f b c
instance GHC.Base.Functor (Generic.Random.Boltzmann.System f a)
instance GHC.Base.Functor (Generic.Random.Boltzmann.ConstModule r)
instance GHC.Num.Num r => Generic.Random.Boltzmann.Embed (Generic.Random.Boltzmann.ConstModule r) m
instance GHC.Num.Num r => GHC.Base.Applicative (Generic.Random.Boltzmann.ConstModule r)
instance GHC.Num.Num r => GHC.Base.Alternative (Generic.Random.Boltzmann.ConstModule r)
instance GHC.Num.Num r => Generic.Random.Boltzmann.Module (Generic.Random.Boltzmann.ConstModule r)
instance GHC.Base.Functor m => GHC.Base.Functor (Generic.Random.Boltzmann.Weighted m)
instance Generic.Random.Internal.Types.MonadRandomLike m => Generic.Random.Boltzmann.Embed (Generic.Random.Boltzmann.Weighted m) m
instance Generic.Random.Internal.Types.MonadRandomLike m => GHC.Base.Applicative (Generic.Random.Boltzmann.Weighted m)
instance Generic.Random.Internal.Types.MonadRandomLike m => GHC.Base.Alternative (Generic.Random.Boltzmann.Weighted m)
instance Generic.Random.Internal.Types.MonadRandomLike m => Generic.Random.Boltzmann.Module (Generic.Random.Boltzmann.Weighted m)
instance GHC.Base.Functor f => GHC.Base.Functor (Generic.Random.Boltzmann.Pointiful f)
instance Generic.Random.Boltzmann.Embed f m => Generic.Random.Boltzmann.Embed (Generic.Random.Boltzmann.Pointiful f) m
instance Generic.Random.Boltzmann.Module f => GHC.Base.Applicative (Generic.Random.Boltzmann.Pointiful f)
instance Generic.Random.Boltzmann.Module f => GHC.Base.Alternative (Generic.Random.Boltzmann.Pointiful f)
instance Generic.Random.Boltzmann.Module f => Generic.Random.Boltzmann.Module (Generic.Random.Boltzmann.Pointiful f)