| Safe Haskell | Safe-Inferred |
|---|---|
| Language | Haskell2010 |
Constrained.SumList
Description
Operations for generating random elements of Num like types, that sum to a particular total.
The class Foldy (defined in the TheKnot.hs) gives the operations necessary to do this.
In this module we define the helper functions necessary to define the methods of the Foldy class.
The helper functions do not need to know about the Foldy class, and are not dependent upon any of
the mutually recursive operations defined in TheKnot, except the operations defined in the Complete class.
That class is defined in this module, but the instance for that class is made in TheKnot.
Synopsis
- class HasSpec a ⇒ Complete a where
- simplifyA ∷ Specification a → Specification a
- genFromSpecA ∷ ∀ m. (HasCallStack, HasSpec a, MonadGenError m) ⇒ Specification a → GenT m a
- theAddA ∷ Numeric a ⇒ IntW '[a, a] a
- noNegativeValues ∷ ∀ a. (Num a, Eq a, MaybeBounded a) ⇒ Bool
- knownUpperBound ∷ (TypeSpec a ~ NumSpec a, Ord a, Enum a, Num a, MaybeBounded a) ⇒ Specification a → Maybe a
- knownLowerBound ∷ (TypeSpec a ~ NumSpec a, Ord a, Enum a, Num a, MaybeBounded a) ⇒ Specification a → Maybe a
- isEmptyNumSpec ∷ (TypeSpec a ~ NumSpec a, Ord a, Enum a, Num a, MaybeBounded a) ⇒ Specification a → Bool
- enumerateInterval ∷ (Enum a, Num a, MaybeBounded a) ⇒ NumSpec a → [a]
- genNumList ∷ ∀ a m. (MonadGenError m, Arbitrary a, Integral a, MaybeBounded a, TypeSpec a ~ NumSpec a, Random a, Complete a) ⇒ Specification a → Specification a → GenT m [a]
- narrowFoldSpecs ∷ ∀ a. (TypeSpec a ~ NumSpec a, Arbitrary a, Integral a, Random a, MaybeBounded a, Complete a) ⇒ (Specification a, Specification a) → (Specification a, Specification a)
- narrowByFuelAndSize ∷ ∀ a. (TypeSpec a ~ NumSpec a, Arbitrary a, Integral a, Random a, MaybeBounded a, Complete a) ⇒ a → Int → (Specification a, Specification a) → (Specification a, Specification a)
- genListWithSize ∷ ∀ a m. (Complete a, TypeSpec a ~ NumSpec a, MonadGenError m, Random a, Integral a, Arbitrary a, MaybeBounded a, Complete Integer, TypeSpec Integer ~ NumSpec Integer) ⇒ Specification Integer → Specification a → Specification a → GenT m [a]
- pickPositive ∷ ∀ t m. (Integral t, Random t, MonadGenError m, TypeSpec t ~ NumSpec t, Complete t) ⇒ Specification t → t → Integer → GenT m [t]
- pickNegative ∷ ∀ t m. (Integral t, Complete t, Random t, MonadGenError m, TypeSpec t ~ NumSpec t) ⇒ Specification t → t → Integer → GenT m [t]
- specName ∷ ∀ a. HasSpec a ⇒ Specification a → String
- predSpecPair ∷ ∀ a. HasSpec a ⇒ Specification a → (String, a → Bool)
- minFromSpec ∷ ∀ n. (Ord n, Complete n, TypeSpec n ~ NumSpec n) ⇒ n → Specification n → n
- maxFromSpec ∷ ∀ n. (Ord n, Complete n, TypeSpec n ~ NumSpec n) ⇒ n → Specification n → n
- data Solution t
- concatSolution ∷ Show t ⇒ t → t → String → t → Int → [Solution t] → Solution t
- newtype Cost = Cost Int
- firstYesG ∷ Monad m ⇒ Solution t → (x → Cost → m (Cost, Solution t)) → [x] → Cost → m (Cost, Solution t)
- noChoices ∷ Show t ⇒ Cost → String → t → t → t → Int → [(t, t)] → Solution t
- splitsOf ∷ Integral b ⇒ b → [(b, b)]
- pickAll ∷ ∀ t. (Show t, Integral t, Random t) ⇒ t → t → (String, t → Bool) → t → Int → Cost → Gen (Cost, Solution t)
- doSplit ∷ (Random t, Show t, Integral t) ⇒ t → t → (String, t → Bool) → t → [(t, t)] → (Int, Int) → Cost → Gen (Cost, Solution t)
- smallSample ∷ (Random t, Integral t) ⇒ t → t → t → t → Int → Gen [(t, t)]
- fair ∷ (Random a, Integral a) ⇒ a → a → Int → Int → Bool → Gen [a]
- logRange ∷ Integral a ⇒ a → (a, a)
- logish ∷ Integral t ⇒ t → t
Documentation
class HasSpec a ⇒ Complete a where Source #
Minimal complete definition
Methods
simplifyA ∷ Specification a → Specification a Source #
genFromSpecA ∷ ∀ m. (HasCallStack, HasSpec a, MonadGenError m) ⇒ Specification a → GenT m a Source #
Instances
| Numeric a ⇒ Complete a Source # | |
Defined in Constrained.TheKnot Methods simplifyA ∷ Specification a → Specification a Source # genFromSpecA ∷ ∀ (m ∷ Type → Type). (HasCallStack, HasSpec a, MonadGenError m) ⇒ Specification a → GenT m a Source # | |
noNegativeValues ∷ ∀ a. (Num a, Eq a, MaybeBounded a) ⇒ Bool Source #
knownUpperBound ∷ (TypeSpec a ~ NumSpec a, Ord a, Enum a, Num a, MaybeBounded a) ⇒ Specification a → Maybe a Source #
knownLowerBound ∷ (TypeSpec a ~ NumSpec a, Ord a, Enum a, Num a, MaybeBounded a) ⇒ Specification a → Maybe a Source #
isEmptyNumSpec ∷ (TypeSpec a ~ NumSpec a, Ord a, Enum a, Num a, MaybeBounded a) ⇒ Specification a → Bool Source #
enumerateInterval ∷ (Enum a, Num a, MaybeBounded a) ⇒ NumSpec a → [a] Source #
Note: potentially infinite list
genNumList ∷ ∀ a m. (MonadGenError m, Arbitrary a, Integral a, MaybeBounded a, TypeSpec a ~ NumSpec a, Random a, Complete a) ⇒ Specification a → Specification a → GenT m [a] Source #
narrowFoldSpecs ∷ ∀ a. (TypeSpec a ~ NumSpec a, Arbitrary a, Integral a, Random a, MaybeBounded a, Complete a) ⇒ (Specification a, Specification a) → (Specification a, Specification a) Source #
Arguments
| ∷ ∀ a. (TypeSpec a ~ NumSpec a, Arbitrary a, Integral a, Random a, MaybeBounded a, Complete a) | |
| ⇒ a | Fuel |
| → Int | Integer |
| → (Specification a, Specification a) | |
| → (Specification a, Specification a) |
genListWithSize ∷ ∀ a m. (Complete a, TypeSpec a ~ NumSpec a, MonadGenError m, Random a, Integral a, Arbitrary a, MaybeBounded a, Complete Integer, TypeSpec Integer ~ NumSpec Integer) ⇒ Specification Integer → Specification a → Specification a → GenT m [a] Source #
Generate a list with sizeSpec elements, that add up to a total that conforms
to foldSpec. Every element in the list should conform to elemSpec
pickPositive ∷ ∀ t m. (Integral t, Random t, MonadGenError m, TypeSpec t ~ NumSpec t, Complete t) ⇒ Specification t → t → Integer → GenT m [t] Source #
pickNegative ∷ ∀ t m. (Integral t, Complete t, Random t, MonadGenError m, TypeSpec t ~ NumSpec t) ⇒ Specification t → t → Integer → GenT m [t] Source #
total can be either negative, or 0. If it is 0, we want count numbers that add to zero
specName ∷ ∀ a. HasSpec a ⇒ Specification a → String Source #
predSpecPair ∷ ∀ a. HasSpec a ⇒ Specification a → (String, a → Bool) Source #
minFromSpec ∷ ∀ n. (Ord n, Complete n, TypeSpec n ~ NumSpec n) ⇒ n → Specification n → n Source #
The smallest number admitted by the spec, if we can find one.
if not return the defaultValue dv
maxFromSpec ∷ ∀ n. (Ord n, Complete n, TypeSpec n ~ NumSpec n) ⇒ n → Specification n → n Source #
The largest number admitted by the spec, if we can find one.
if not return the defaultValue dv
concatSolution ∷ Show t ⇒ t → t → String → t → Int → [Solution t] → Solution t Source #
The basic idea is to concat all the Yes's and skip over the No's. The one wrinkle is if everything is No, then in that case return an arbitrary one of the No's. This can be done in linear time in the length of the list. Call that length n. Check for all No. This takes time proportional to n. If it is true return one of them. If it is not all No, then concat all the Yes, and skip all the No. We find the first No (if it exist), and all the Yes by partitioning the list This is similar in spirit to Constrained.GenT.catGEs, but doesn't require a a Monad to escape on the first No.
Constructors
| Cost Int |
firstYesG ∷ Monad m ⇒ Solution t → (x → Cost → m (Cost, Solution t)) → [x] → Cost → m (Cost, Solution t) Source #
splitsOf ∷ Integral b ⇒ b → [(b, b)] Source #
Given count, return a list of pairs, that add to count
splitsOf 6 --> [(1,5),(2,4),(3,3)].
Note we don't return reflections like (5,1) and (4,2),
as they have the same information as (1,5) and (2,4).
pickAll ∷ ∀ t. (Show t, Integral t, Random t) ⇒ t → t → (String, t → Bool) → t → Int → Cost → Gen (Cost, Solution t) Source #
Given a Path, find a representative solution, ans, for that path, such that
1) (length ans) == count,
2) (sum ans) == total
3) (all p ans) is True
What is a path?
Suppose i==5, then we recursively explore every way to split 5 into
split pairs that add to 5. I.e. (1,4) (2,3), then we split each of those.
Here is a picture of the graph of all paths for i==5. A path goes from the root '5'
to one of the leaves. Note all leaves are count == '1 (where the solution is '[total]').
To solve for 5, we could solve either of the sub problems rooted at 5: [1,4] or [2,3].
5
|
[1,4]
| |
| [1,3]
| | |
| | [1,2]
| | |
| | [1,1]
| |
| [2,2]
| | |
| | [1,1]
| |
| [1,1]
|
[2,3]
| |
| [1,2]
| |
| [1,1]
[1,1]
In pickAll will explore a path for every split of count
so if it returns (No _), we can be somewhat confidant that no solution exists.
Note that count of 1 and 2, are base cases.
When count is greater than 1, we need to sample from [smallest..total],
so smallest better be less that or equal to total
doSplit ∷ (Random t, Show t, Integral t) ⇒ t → t → (String, t → Bool) → t → [(t, t)] → (Int, Int) → Cost → Gen (Cost, Solution t) Source #
smallSample ∷ (Random t, Integral t) ⇒ t → t → t → t → Int → Gen [(t, t)] Source #
If the sample is small enough, then enumerate all of it, otherwise take a fair sample.
fair ∷ (Random a, Integral a) ⇒ a → a → Int → Int → Bool → Gen [a] Source #
Generates a fair sample of numbers between smallest and largest.
makes sure there are numbers of all sizes. Controls both the size of the sample
and the precision (how many powers of 10 are covered)
Here is how we generate one sample when we call (fair (-3455) (10234) 12 3 True)
raw = [(-9999,-1000),(-999,-100),(-99,-10),(-9,-1),(0,9),(10,99),(100,999),(1000,9999),(10000,99999)]
ranges = [(-3455,-1000),(-999,-100),(-99,-10),(-9,-1),(0,9),(10,99),(100,999),(1000,9999),(10000,10234)]
count = 4
largePrecision = [(10000,10234),(1000,9999),(100,999)]
smallPrecision = [(-3455,-1000),(-999,-100),(-99,-10)]
answer generated = [10128,10104,10027,10048,4911,7821,5585,2157,448,630,802,889]
isLarge==True means be biased towards the large end of the range,
isLArge==False means be biased towards the small end of the range,