N      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~      None*,29:;<=DIQRTfFor convenience.A  BaseCases n ( a); constraint basically provides the list of values of type a with depth at most n.Peano-encoded natural numbers. Generic ArbitraryNPick 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, 0 tends to produce big values. For instance for Tree a. values are finite but the average number of Leaf and Node constructors is infinite.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) ]The size parameter of  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 type of  has an ambiguous n7 parameter; it is a type-level natural number of type &. That number determines the maximum depth, of terms that can be used to end recursion.You'll need the TypeApplications and  DataKinds extensions. %genericArbitraryFrequency' @n weightsWith n ~ 't, 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' @'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] 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 <*> arbitraryfTo 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.5For instance, if we want to generate a value of type Tree ()/, there is a value of depth 1 (represented by ' '%) 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 Tree8 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]Like /, but with uniformly distributed constructors.0 %List of weights for every constructor%List of weights for every constructor !"#$%&'()*+,-./ 0/ .-,+*)( '& %$#"! $    !"#$%&'()*+,-./ None  None %&IOQRT33 mn defines basic components to build generators, allowing the implementation to remain abstract over both the  type and  instances.For the latter, the wrapper :- is provided to avoid overlapping instances.4DCalled for every constructor. Counter for ceiled rejection sampling.5doubleR upperBound: generates values in [0, upperBound].6integerR upperBound: generates values in [0, upperBound-1].7Default Int generator.8Default Double generator.9Default Char generator.=,Internal transformer for rejection sampling. 'ReaderT Size (StateT Size (MaybeT m)) a@#Size as the number of constructors.GMain constructor for B.HMain constructor for A.I 0coerceAlias :: Alias m -> Alias (AMonadRandom m)J 6coerceAliases :: [Alias m] -> [Alias (AMonadRandom m)]K composeCast f g = f . gTSet lower bound]Dummy instance for debugging.^Dummy instance for debugging.,3456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^"3987456:;<=>?@ABCDEFGHIJKLMNOPQRST,EFD^BCA]GHIJKLMNOPQRS@=>?\[ZYT:;<X3456789WVU 3456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^None !":DORTi Assuming p . f9 is satisfied only for positive values in some interval (0, r], find f r.bcdefghibcdefghibcdefghibcdefghiSafenpartitions k n+: lists of non-negative integers of length n! with sum less than or equal to k.oBinomial coefficient. Abinomial n k == factorial n `div` (factorial k * factorial (n-k))pMultinomial coefficient. Emultinomial n ps == factorial n `div` product [factorial p | p <- ps]mnopmnopmnopmnopNone !"%&05:OTrMaps a key representing a type a+ (or one of its pointings) to a generator m a.s?An oracle gives the values of the generating functions at some x.tType of .u"The type of the first argument of .A pair C i k represents the k$-th "pointing" of the type at index i, with generating function  C_i[k](x)._We build a dictionary which reifies type information in order to create a Boltzmann generator. We denote by n (or () 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 4 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 .The order (or  valuationP) of a power series is the index of the first non-zero coefficient, called the leading coefficient.Number of registered types-Number of iterations of the pointing operatorMap from types to indices!Inverse map from indices to typesInverse map to aliases.Structure of types and their pointings (up to , initially 0)iPrimitive types and empty types are mapped to an empty constructor list, and can be distinguished using  on the E associated to it by .=The integer is a multiplicity which can be > 1 for pointings. 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.`Degrees of the generating functions, when applicable: greatest size of objects of a given type.@Find all types that may be types of subterms of a value of type a.7This will loop if there are infinitely many such types.Primitive datatypes have C(x) = x2: they are considered as having a single object (lCoef ) of size 1 (order)).*Traversal of the definition of a datatype.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 v' is unrolled here for maximum laziness.Sum of a list of series.$Leading term of a product of series.Pointing operator. Populates a % with one more level of pointings. (# 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'B Tree' Tree -- Point 1 at the root, point 2 to the left | Node'1'C Tree Tree' -- Point 1 at the root, point 2 to the right | Node'0'60 Tree'' Tree -- Points 1 and 2 to the left | Node'0'E1 Tree' Tree' -- Point 1 to the left, point 2 to the right | Node'1'E0 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 iq-th subterm), the multiplicity of the constructor paired with that distribution is the multinomial coefficient multinomial k [p_1, ..., p_c].Find the value of x6 such that the average size of the generator for the k-1-th pointing is equal to size5, and produce the associated oracle. If the size is Nothing!, find the radius of convergence.AThe 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./Generating function definition. This defines a Phi_i[k] function associated with the k"-th pointing of the type at index i , such that: iC_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) = x2: they are considered as having a single object (lCoef ) of size 1 (order)).&Build all involved generators at once.&Generators of values of minimal sizes. dd ? (listCs dd !! i) = i dd ? (dd ?! i) = i<qrstuvwxyz{|}~8qrstuvwxyz{|}~<}~|z{yvwxutsrq.qrstuvwxyz{|}~ None!"22The size of a value is its number of constructors.Here, however, the d type is interpreted differently to make better use of QuickCheck's size parameter provided by the  S combinator, so that we generate non-trivial data even at very small size values.4For infinite types, with objects of unbounded sizes  > minSize, given a parameter  delta :: 5, 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]6, the target expected size is obtained by clamping a  to [0, 99]! and applying an affine mapping.Number of pointing iterations.Sized generator.For documentation. 'epsilon' = 0.1Default approximation ratio. ,(size * (1 - epsilon), size * (1 + epsilon))None    :: Int -> Gen a < .  ::  MonadRandom m => Int -> m a "Singular ceiled rejection sampler.   :: Int -> Gen a < .  ::  MonadRandom m => Int -> m a Generator of pointed values.!Pointed generator with rejection.2Generator with rejection and dynamic average size.Pointed generator.!Pointed generator with rejection.1Ceiled rejection sampler with given average size.-Basic boltzmann sampler with no optimization.$Boltzmann sampler without rejection.!Boltzmann sampler with rejection.'3987456:;<ABCGHIJ'3456789:;<GHIJBCANone!"%&0259:;<=DORTf defines a product, B defines an addition, with scalar multiplication we get a module.QThis typeclass allows to directly tweak weights in the oracle by chosen factors.Scalar embedding.Scalar multiplication.!A natural transformation between f and m?, Index of typePoints#Expected size (or singular sampler) Index of typePoints#Expected size (or singular sampler)     ,          3   !"#$%&'()*+,-./0123456789:;<=>?@ABCCDEEFGHIIJKKLMNOPQRSTUVWXYZ[\]^_`abcdefgghijklmnopqrstuvwxyz{|}}~z         -generic-random-0.2.0.0-L3F1Aj3Z0F81JsJL5QlOYcGeneric.Random.Internal.GenericGeneric.Random.Internal.TypesGeneric.Random.Internal.SolverGeneric.Random.Internal.CommonGeneric.Random.Internal.OracleGeneric.Random.Internal.DataGeneric.Random.DataGeneric.Random.BoltzmannGeneric.Random.GenericTest.QuickChecksized BaseCases' BaseCases baseCasesNatZSTaggedunTagged GAProduct gaProductGASumgaSumGAgaUnsizedSizedGen'unGen'FrequnFreqgenericArbitrarygenericArbitraryFrequencygenericArbitraryFrequency'genericArbitrary'liftGengArbitrarySingle baseCases'$fBaseCasesn:*:$fBaseCasesn:+:$fBaseCasesSK1$fBaseCasesZK1$fBaseCasesnM1$fBaseCasesnU1$fGAProduct:*: $fGAProductM1$fGASumsizedM1$fGASumsized:+: $fGASized:*:$fGAUnsized:*:$fGAUnsized:+: $fGASized:+: $fGAsizedM1 $fGAsizedK1 $fGAsizedU1$fApplicativeFreq $fFunctorFreq $fFunctorGen'$fApplicativeGen'MonadRandomLikeincrdoubleRintegerRintdoublechar AMonadRandom asMonadRandomRejectT unRejectTSizeAliasRAlias SomeData'SomeDataaliasaliasR coerceAlias coerceAliases composeCastMcastM unSomeData applyCast castError withProxyreproxy proxyType someData' runRejectT$fMonadRandomLikeAMonadRandom$fMonadRandomLikeRejectT$fMonadRandomLikeGen$fMonadTransAMonadRandom$fMonadTransRejectT$fMonadRejectT$fApplicativeRejectT$fFunctorRejectT $fShowAlias$fShowSomeData$fFunctorAMonadRandom$fApplicativeAMonadRandom$fMonadAMonadRandom SolveArgsaccuracy numIterations defSolveArgsfindZero fixedPointsearch $fEqSolveArgs$fOrdSolveArgs$fShowSolveArgs frequencyWith partitionsbinomial multinomialSmallGenerators GeneratorsOracleAMapGUnfoldZeroSuccIxAliasedC'ACCDataDefcountpointsindexxednixedni'typeslTermdegreenatToIntinfinitydataDef collectTypes primOrder primOrder' primlCoef collectTypesM chaseType traverseType traverseType'lPluslSumlMullProd maxDegreepoint makeOraclephimakeGeneratorssmallGeneratorsgeneratedefGen?listCsix?! getGeneratorgetSmallGenerator#! $fMonoidNat$fHashableAliased $fHashableAC $fHashableC $fEqAliased $fOrdAliased $fShowAliased$fGenericAliased$fEqAC$fOrdAC$fShowAC $fGenericAC$fEqC$fOrdC$fShowC $fGenericC$fEqNat$fOrdNat $fShowNat $fShowDataDefSize'PointsSGminSizemaxSizeMrunSG runSmallGrangeSGapplySGmakemakeRrescaleapplyapplyRrescaleIntervalepsilon tolerancememo sparseSized $fFunctorSG generatorSR generatorP generatorPR generatorR generatorP' generatorPR' generatorR' generator'generatorSRWithgeneratorPRWithgeneratorPWithgeneratorRWithgeneratorPWith'generatorPRWith'generatorRWith'generatorWith' generatorM generatorMR generator_ generatorR_ PointifulWeighted ConstModule unConstModuleSystemdimsys'EndoModuleScalarscalar<.>EmbedemapembedsyssolvesizedGenerator solveSizedweighted runWeightedsfix unPointiful$fModulePointiful$fAlternativePointiful$fApplicativePointiful$fEmbedPointifulm$fFunctorPointiful$fModuleWeighted$fAlternativeWeighted$fApplicativeWeighted$fEmbedWeightedm$fFunctorWeighted$fModuleConstModule$fAlternativeConstModule$fApplicativeConstModule$fEmbedConstModulem$fFunctorConstModule$fFunctorSystembase GHC.GenericsRep'QuickCheck-2.9.1-ADKJfTsJVEWJp7VC229wViTest.QuickCheck.GenGen*MonadRandom-0.4.2.3-BeY4MXl2TWH5X5ex76pU0BControl.Monad.Random.Class MonadRandom Data.Datagunfold dataTypeRepGHC.Base Applicative Alternative