Random instances for Ratio

There is currently no instances for Ratio data type that can give us random values

Edit: - It looks like we are in a agreement that Uniform and UniformRange instances are not possible for Ratio. Question then is, should we add a Random instance, which doesn't really promise uniformity?

I can see a reasonable Uniform instance for integral types, which excludes the zero denominator:

instance (Integral a, Uniform a) => Uniform (Ratio a) where
  uniformM g = do
    n <- uniformM g
    let notZero = do
          d <- uniformM g
          if d == 0 then notZero else pure d
    (n %) <$> notZero

An efficient version for UniformRange needs some thought.

Note that neither Uniform, nor UniformRange would be able to generate Rational. This means that we can attempt and cook up such instance for Random

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

@Shimuuar It is uniform as far as the Ratio Word3 is concerned. It is just as uniform as selecting uniformly from data RGB = Red | Green | Blue data 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 Uniform about 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 have Random class 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 1 7 times out of 56, and 7 only 1 of 56.

The problem is that Ratio Word3 has 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-Uniform inhabitants-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 Ratio type?

For Ratio Word one can generate n and d; if gcd n d == 1 then return n % d, otherwise reject them and generate new ones. But things may become more complicated for Ratio Int because of signs and minBound /= negate maxBound, need to think more about it.

In my experience Ratio Int / Ratio Word are 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.

@Shimuuar

I don't think anyone would expect such semantics.

2 % 4 and 1 % 2 are equal inhabitants as far as Ratio is 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

@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-L508

CC @NorfairKing

@lehins

@lehins For the record, this is how genvalidity generates Ratios:
https://github.com/NorfairKing/validity/blob/cfe18e509a7c3298a15751c5889254cf0650cbc2/genvalidity/src/Data/GenValidity.hs#L718-L728

    genValid = (do
      n <- genValid
      d <- (genValid `suchThat` (> 0))
      pure $ n :% d) `suchThat` isValid

You can probably generate the denominator more easily if you assume Num and use abs.

@Shimuuar

@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.

FWIW if I'd ask a library to generate random Ratio in 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.

Well 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 Ratio data 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 Ratio from base :D

It 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 % maxBound but then one have to convert to Ratio Integer since basically any operation could overflow denominator.

Ratio a, when a has 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 define instance Random Rational just applying toRational to Doubles in [0, 1].

Ratio 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 random generators 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.choose for Rational which relies on Random.
Here is why we can't have a uniform distribution on the rationals, between 0 and 1, say:

Any Random a instance 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 observing const True is 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 x is. (This holds even when (+x) overflows!) In particular, for discrete types (with an Eq instance), 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 -> Bool has 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 weight w > 0 then 1 would be the sum of infinitely many w's, which is absurd.

I therefore suggest to close this issue since UniformRange Rational is provably impossible to implement.

@olafklinke

@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 Random instance, which doesn't really promise uniformity?

This would make it possible to generate Rational with choose in 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 the random package.

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 someDistribution it 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 % 3

The implementation of approxRational does 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 about Ratio #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, the sized parameter n restricts the rational to fractions in the interval [-n,n] with denominator at most n, which is a finite set.

Navigation Menu

Repository navigation

`Random` instances for `Ratio` #75

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Random instances for Ratio #75

Description

Activity

Shimuuar commented on Jun 30, 2020

lehins commented on Jun 30, 2020

Shimuuar commented on Jun 30, 2020

Bodigrim commented on Jun 30, 2020

lehins commented on Jun 30, 2020

Bodigrim commented on Jun 30, 2020

Shimuuar commented on Jun 30, 2020

lehins commented on Jun 30, 2020

lehins commented on Jun 30, 2020

NorfairKing commented on Jun 30, 2020

Shimuuar commented on Jun 30, 2020

qnikst commented on Jun 30, 2020

lehins commented on Jun 30, 2020

Shimuuar commented on Jun 30, 2020

lehins commented on Jun 30, 2020

Shimuuar commented on Jun 30, 2020

Bodigrim commented on Jun 30, 2020

lehins commented on Jun 30, 2020

NorfairKing commented on Jun 30, 2020

Shimuuar commented on Jul 1, 2020

olafklinke commented on Sep 19, 2025

lehins commented on Sep 19, 2025

Shimuuar commented on Sep 19, 2025

olafklinke commented on Sep 20, 2025

Shimuuar commented on Sep 21, 2025

olafklinke commented on Sep 22, 2025

idontgetoutmuch commented on Sep 22, 2025

olafklinke commented on Sep 22, 2025

Metadata

Metadata

Assignees

Labels

Type

Projects

Milestone

Relationships

Development

Issue actions

`Random` instances for `Ratio` #75