Which distribution is realized by `choose`?

[RalfJung]

The choose functions say that they are picking an element at random, but they don't say according to which distribution. Obviously knowing the distribution is crucial to properly using this function, so I hope this gap in the docs can be fixed.

For slices I strongly assume the distribution is uniform, but for choosing from an iterator, this is much less obvious -- will the distribution always be uniform even if the size_hint is very imprecise? What if the size_hint is wrong?

[dhardy]

From memory, yes the distributions are uniform, even for iterators. size_hint enables optimisation (though there was even one request not to use it there due to how this affects the random number stream).

Okay, docs need improvement.

[dhardy]

The docs do at least mention that complexity is O(n) in general, but that O(1) is possible with a correct hint. I think the only thing needing improvement is a mention of "uniform".

[RalfJung]

I'm pretty sure a wrong size_hint also affects the distribution. If I have an iterator that yields 10 elements, and my size_hint says (5, Some(5)), then rand will pick an element uniformly at random from the first 5 elements.

So it seems like the distribution is uniform as long as size_hint (and nth) all behave according to the usual contract -- they can be arbitrarily imprecise, but they must not be outright wrong. Logic bugs are allowed for such wrong Iterator, but it might still be worth mentioning that?

[dhardy]

Agreed, uniformity assumes that size_hint is correct. I believe this is acceptable (memory safety is not affected).

Looking at the algorithm, it will in most cases ignore elements beyond an upper bound. It may also return None where fewer elements are present than indicated by the lower bound.

[RalfJung]

Agreed, uniformity assumes that size_hint is correct. I believe this is acceptable (memory safety is not affected).

Yeah I agree. It might be nice to mention this in the docs though -- contract violations of the Iterator trait can not only lead to panics but also to silently generating the wrong distribution.