Add additional iterator traits for DistIter

[Lucretiel]

rand/src/distributions/mod.rs

Lines 302 to 315 in 7aec8e2

	impl<'a, D, R, T> Iterator for DistIter<'a, D, R, T>
	where D: Distribution<T>, R: Rng + 'a
	{
	type Item = T;
	#[inline(always)]
	fn next(&mut self) -> Option<T> {
	Some(self.distr.sample(self.rng))
	}
	fn size_hint(&self) -> (usize, Option<usize>) {
	(usize::max_value(), None)
	}
	}

The DistIter iterator might benefit from the following additional implementations:

• DoubleEndedIterator
• TrustedLen
• FusedIterator

Additionally, it's recommended that custom iterators implement try_fold, which is the base method used for all other non-lazy iterator operations.

[dhardy]

Thanks for the tips.

We can't implement DoubleEndedIterator correctly for anyone who cares about reproducibility, so I'd prefer to leave that out.

Is there any point implementing try_fold explicitly? The following works, but since the unwrap is trivial and next is marked with inline(always), the default implementation will probably produce equivalent code?

impl<'a, D, R, T> Iterator for DistIter<'a, D, R, T>
    where D: Distribution<T>, R: Rng + 'a
{
    type Item = T;

    #[inline(always)]
    fn next(&mut self) -> Option<T> {
        Some(self.distr.sample(self.rng))
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        (usize::max_value(), None)
    }
    
    #[cfg(features = "nightly")]
    fn try_fold<B, F, R>(&mut self, mut init: B, f: F) -> R
    where
        F: FnMut(B, Self::Item) -> R,
        R: Try<Ok = B>
    {
        loop {
            init = f(init, self.next().unwrap())?;
        }
    }
}

[Lucretiel]

I mean, I'd do it a bit simpler:

fn try_fold<B, F, R>(&mut self, mut init: B, f: F) -> R
    where
        F: FnMut(B, Self::Item) -> R,
        R: Try<Ok = B>
    {
        loop {
            init = f(init, self.distr.sample(self.rng))?;
        }
    }

It ends up being the same, but frees up some budget for the optimizer.

Regarding DoubleEndedIterator and reproducibility: it's unclear to me how it's the case that it breaks reproducibility, since the same sequence of next() and next_back() calls will cause the same sequence of output. Inserting a random call to next_back() between 2 calls to next() is no different than inserting a random call to next() between those two calls. I don't really see the harm, and it allows for some additional patterns to be used, such as:

// Get a random number for each letter, in reverse
'a'...='z'.zip(my_dist.sample_rng(rng)).rev()
// Yes, you could rev THEN sample, but my point remains that I think it's worth having it available.

[burdges]

I think TrustedLen depends on all of D, R, T technically since sampling must consume exact amounts of randomness from R. Worse, there are Rngs for which we cannot know the exact output size, presumably mostly exceed usize, but not ReadRng.

Yes, there are many "reproducible" scenarios in which this works, making that term questionable, but DistIter clearly fails conventional assumptions on DoubleEndedIterator:

Right now, Take does not satisfy DoubleEndedIterator, but it could do so after future support for seekable iterators, so that..

let mut v = my_dist.sample_iter(&mut rng.clone()).take(5).collect::<Vec<_>>();
v.reverse();
assert_neq!(v, my_dist.sample_iter(&mut rng.clone()).take(5).rev().collect());

Worse, if you rev a DistIter then you encounter dangerous correlations between the sequence's beginning and end:

let mut a = my_dist.sample_iter(&mut rng.clone());
let mut b = my_dist.sample_iter(&mut rng.clone()).rev();
loop { assert_eq!(a.next(),b.next()); }

If you need these traits then you could build specific Rngs that actually satisfy them.

[dhardy]

There's also mixed usage of next and next_back. In theory for a double-ended iterator it shouldn't matter if let a = iter.next(); let b = iter.next_back(); is rearranged to let b = iter.next_back(); let a = iter.next();, but we can't implement DoubleEndedIterator such that it respects this.

It ends up being the same, but frees up some budget for the optimizer.

By increasing code complexity for us, with basically zero real-world gain (I assume; feel free to prove me wrong). Personally I believe we should prefer more readable code in this circumstance.

I think TrustedLen depends on all of D, R, T

The distribution D is accessed via const &D so in theory this is not important, besides which it could only "stop" by panicking since sample does not return a Result. The RNG R could indeed have finite length, but we generally assume RNGs have infinite length and next_u32 etc. reflect this, as well as sample. Given that a short ReadRng must indicate out-of-data by panicking I think it's better to view such failures as being in the same category as out-of-memory: it's an exceptional circumstance you can't deal with, so don't even try.

TrustedLen docs say:

The iterator must produce exactly the number of elements it reported or diverge before reaching the end.