Repository navigation
Random instances for Ratio #75
Description
Activity
It isn't uniform. Let take for sake of simpliciti
Ratio Word3. In this case we will generate with equal probability each value in the list:
liftA2 (%) [0..7] [1..7]. They cover range [0, 7] but only 5 values are in [3.5 .. 7] range.@Shimuuar It is uniform as far as the
Ratio Word3is concerned. It is just as uniform as selecting uniformly fromdata RGB = Red | Green | Bluedata type with equal probability. We generate all possible values that a data type can have with uniform probability.I understand that with respect to the actual rational numbers over the infinite space, this is not uniform, but the type is not infinite. That means we need to decide. Is
Uniformabout math and real values, or it is about the uniformity of types? I am fine with either choice, by the way, because we do still haveRandomclass that allows us to deal with this issue.When it come to numbers uniform usually understood as distributed on number line with uniform density. For Ints & Words we work on uniform grid so notions of uniform density and generate every inhabitant with equal probability coincide. For floats we try to approximate density and abandon every inhabitant with equal probability.
But this instance is not uniform in either sense! It generates
17 times out of 56, and7only 1 of 56.The problem is that
Ratio Word3has not 8*(8-1)=56, but only 36 inhabitants: 0 and 1 appear 7 times of 56, 1/2 and 2 - thrice; 1/3, 2/3, 3/2 and 3 - twice. It is certainly non-Uniforminhabitants-wise.I see what you mean. So my suggested implementation is bogus. That's fine. Question is can we come up with a sensible implementation(s) for the
Ratiotype?For
Ratio Wordone can generatenandd; ifgcd n d == 1then returnn % d, otherwise reject them and generate new ones. But things may become more complicated forRatio Intbecause of signs andminBound /= negate maxBound, need to think more about it.In my experience
Ratio Int/Ratio Wordare of limited utility, because it is too easy to get an overflow in denominator.Also I think that approach "generate every inhabitant with equal probability" is just a giant footgun. I don't think anyone would expect such semantics.
I don't think anyone would expect such semantics.
2 % 4and1 % 2are equal inhabitants as far asRatiois concerned, because values are normalized. So here we are really talking about generating all valid inhabitants with equal probability.@Shimuuar What would you expect if someone asked you: Generate a random rational number for me please?
@Bodigrim I remember helping out a friend with this and he came up with this validation for
Ratio: https://github.com/NorfairKing/validity/blob/cfe18e509a7c3298a15751c5889254cf0650cbc2/validity/src/Data/Validity.hs#L500-L508CC @NorfairKing
@lehins For the record, this is how
genvaliditygenerates Ratios:
https://github.com/NorfairKing/validity/blob/cfe18e509a7c3298a15751c5889254cf0650cbc2/genvalidity/src/Data/GenValidity.hs#L718-L728genValid = (do n <- genValid d <- (genValid `suchThat` (> 0)) pure $ n :% d) `suchThat` isValidYou can probably generate the denominator more easily if you assume
Numand useabs.@Shimuuar What would you expect if someone asked you: Generate a random rational number for me please?
Well I certainly don't expect such questions. But it's impossible to speak about generating random numbers without specifying distribution first. So we either know what we're talking about or person asking such question deserve some ridicule
But then if we have Uniform why nor UniformRange? How UniformRange should work then? It it uses same approach: "generate every inhabitant with equal probability" why then it works differently from Float/Double. They're just a different subset of rationals after all.
Reacted by David FeuerFWIW if I'd ask a library to generate random
Ratioin the place where I don't care much about distribution, I would expect that it has a uniform distribution over requested range, and I would consider non-uniform distribution as a bug.Reacted by Alexey KuleshevichWell I certainly don't expect such questions.
Lol. I am asking you one right now ;) Basically how would you solve it? We need uniform distribution for
Ratiodata type"Don't try to be clever just use doubles". It's question about building unform distributions between two really big numbers (0, maxBound :: Word64) for example. It's very hard problem since it requiring carefully weighting numbers on very uneven grid. I'm not sure it's even possible without excessive lookup tables
"Don't try to be clever just use doubles"
lol. I am already submitting a PR to ghc to remove
Ratiofrom base :DIt is a hard problem, but I don't think it is an unsolvable one. We definitely don't have to decide on it now, so let's think about it and see what we can come up with.
lol. I am already submitting a PR to ghc to remove Ratio from base :D
I'm quite serious BTW. Generating doubles, casting them to Rationals and working with them in case you need to work with them is quite viable approach. Another one is to generate
uniformM % maxBoundbut then one have to convert toRatio Integersince basically any operation could overflow denominator.Reacted by Alexey KuleshevichRatio a, whenahas finite precision, is a very dangerous and unlawful beast. For example,(-11 % 12 :: Ratio Int8) > 13 % 12. I would rather discourage people from using such types, and I bear no interest in providing utilities to work with them.On the other hand, if we decide to give a green light to new instances of
Random, we can defineinstance Random Rationaljust applyingtoRationaltoDoublesin [0, 1].Reacted by Alexey KuleshevichRatio a, when a has finite precision, is a very dangerous and unlawful beast.
Sounds reasonable.
On the other hand, if we decide to give a green light to new instances of Random, we can define instance Random Rational just applying toRational to Doubles in [0, 1].
I like it.
On the other hand, if we decide to give a green light to new instances of Random, we can define instance Random Rational just applying toRational to Doubles in [0, 1].
This would be inappropriate in testing, but there's no reason why
randomgenerators should be used for testing per-se.
As long as this is documented well, I don't really mind, but we might as well just have some functions then, instead of an instance.On the other hand, if we decide to give a green light to new instances of Random, we can define instance Random Rational just applying toRational to Doubles in [0, 1].
That sounds as reasonable choice for Random instance. BTW it's not necessary to involve Doubles we can just use:
n <- (fromIntegral :: Word64 -> Integer) <$> unform return $ n % (2^64-1)
Came here because I was looking for
Test.QuickCheck.chooseforRationalwhich relies onRandom.
Here is why we can't have a uniform distribution on the rationals, between 0 and 1, say:Any
Random ainstance should have an associated probability distribution. Given any observation (event)a -> Bool, the distribution tells us how likely a randomly generated value would fit this observation. Obviously, the probability of observingconst Trueis one. Uniformity means that given a notion to shift observations around, e.g.\x -> event -> event . (+x) :: Num a => a -> (a -> Bool) -> (a -> Bool)then this shift does not change the likelihood of the event, whatever
xis. (This holds even when(+x)overflows!) In particular, for discrete types (with anEqinstance), there are the atomic events(a==)and in all finite integral types such events can be shifted into each other. That is, any atomic event(x==)can be obtained from the event(0==)by shifting with(-x). This is a complicated way to say: All numbers are equally likely to be generated.The rationals are a discrete, countable space. Given any distribution, any event
Rational -> Boolhas a probability (weight) w.r.t. the distribution, and sigma-additivity dictates that if you have a countable set of mutually exclusive events, then the weight of their (disjoint) union is the infinite sum of their individual weights. Let's say that the weight of the rational unit interval is 1. Since the rationals are enumerable, we can express the entire unit interval as the countable disjoint union of events of the form(q==). But if each such event has equal weightw > 0then 1 would be the sum of infinitely manyw's, which is absurd.I therefore suggest to close this issue since
UniformRange Rationalis provably impossible to implement.- changed the title
[-]Instances for `Ratio`[/-][+]`Random` instances for `Ratio`[/+]on Sep 19, 2025 @olafklinke Very good points. I've changed the title of the ticket and added this question that we should collectively answer:
should we add a
Randominstance, which doesn't really promise uniformity?This would make it possible to generate
Rationalwithchoosein quickcheck without violating any laws. Thoughts?Generating uniform rationals is impossible but one could try to generate approximately uniform rationals (for some notion of uniformity). "Approximately" does a lot of heavy lifting here.
Slightly shorter reasoning: in any interval there's infinite number of rational numbers in it. So probability of generating any particular number is zero. And almost all of numbers in the interval have very large denominator. Any practical generator will bias to small denominator. That's good problem to think about on weekend
And almost all of numbers in the interval have very large denominator. Any practical generator will bias to small denominator.
Yes I believe we can have an acceptable generator, at least for the purposes of random testing, if we require uniformity only for events of positive extent, meaning within the specified range, any two intervals of equal non-zero length get the same weight. Here is a rough sketch:
- Start with a given range, e.g.
(a,b) = (0,1). - randomly decide whether to sub-divide the range or not.
- If no, return the simplest rational in the range, i.e. the rational with the smallest denominator.
- If yes, randomly select either the sub-range
((a+b)/2,b)or(a,(a+b)/2)and recurse.
Such a biased procedure would probably not be what a user expects when seeing
UniformRange Rational, whence I think the sketched procedure has no place in therandompackage.- Start with a given range, e.g.
Such procedure could only generate rational with denominators equal to powers of 2. So it's not possible to generate 1/3 which seems wrong.
Another algorithms is to generate integers N,K such that N/K is approximately uniform.
n <- someDistribution k <- uniformR (0, n) return $ k % n
By tweaking size of tail of
someDistributionit becomes easy to tweak "size" of generated rationals.There's no single right way to generate rationals so there shouldn't be instance. But adding functions seems reasonable
Such procedure could only generate rational with denominators equal to powers of 2. So it's not possible to generate 1/3 which seems wrong.
Perhaps my wording was too vague: The "simplest rational' in the interval between the dyadic rationals 1/4 and 3/8 is 1/3, so it does get generated.
>>> Data.Ratio.approxRational (1%4) (1%8) 1 % 3The implementation of
approxRationaldoes not care whether the approximant is smaller or greater, but its body contains an algorithm that yields the simplest rational within any rational interval.This is all very interesting. Floating point numbers are drawn from a finite collection (how about a mantissa of 3 bits and an exponent of 2 bits) but rationals are drawn from a countably infinite collection. Countably infinite means being in direct correspondence with the natural numbers. So if we could randomly select each rational (with equal probability) then we could randomly select a natural number (with equal probability) and that is impossible.
I would think the person wanting to use quick check on rationals could just use a geometric distribution but that is not something that this package need concern itself with.
I have been working in Lean for the last year and here we have the reals with all their properties and the floats with all their peculiarities. Of course the reals are not computable. The Lean equivalent of this package (Random) seems quite rudimentary but I don't think it is much used.
That's a very long-winded way of saying I don't think a Random instance for Ratio should exist but since I don't use Random much these days, perhaps not very much weight should be placed on my opinion.
Another point in favour of closing this issue.
Note there was a bug aboutRatio#356 in the QuickCheck package, but it was fixed. Perhaps arbitrarySizedFractional can serve as guidance on how to sensibly generate random rationals. As I read it, thesizedparameternrestricts the rational to fractions in the interval [-n,n] with denominator at most n, which is a finite set.
There is currently no instances for
Ratiodata type that can give us random valuesEdit: - It looks like we are in a agreement that
UniformandUniformRangeinstances are not possible forRatio. Question then is, should we add aRandominstance, which doesn't really promise uniformity?I can see a reasonable
Uniforminstance for integral types, which excludes the zero denominator:An efficient version for
UniformRangeneeds some thought.Note that neither
Uniform, norUniformRangewould be able to generateRational. This means that we can attempt and cook up such instance forRandom