Implementing SliceRandom::choose_multiple(_weighted) is impossible if you aren't simply forwarding the calls to an inner [T]

[LikeLakers2]

Hi! I'm trying to implement rand::seq::SliceRandom for a custom Vec-like collection I'm building. However, I found myself stuck in trying to implement SliceRandom::choose_multiple.

The collection is set up as follows:

pub struct PaletteVec<T> {
	palette: ::indexset::IndexSet<T>,
	
	// Vec of indices into `self.palette`
	items: Vec<usize>,
}

Getting a T from this collection involves mapping a usize obtained from self.items, to a T obtained from self.palette. In most cases, I can use Iterator::map or Option::map for this.

However, SliceRandom::choose_multiple and SliceRandom::choose_multiple_weighted require me to return a rand::seq::SliceChooseIter. I do not see a way to construct this on my own - the only way to make one is via self.items.choose_multiple(), which would return a usize rather than a T - and I especially do not see a way to implement this such that it maps the usizes to Ts before returning values.

Because I can't return a SliceChooseIter, I can't implement SliceRandom - not unless I decide to put unimplemented!() in the methods that return a SliceChooseIter. This feels like a deficiency in the rand crate, one that I'm unsure how to solve - but I'm also wondering if there's a way around it that I'm unaware of.

So, any help with this, please? Or is this something that would require rand to change how SliceRandom is implemented?

[dhardy]

You're right; we didn't design this for extension by third-party crates. Changes to Rand are required.

Some possibilities:

• Add a public constructor to SliceChooseIter. It only requires a slice and an iterator over usize so this should be fine.
• Use GATs; choose_multiple returns Self::SliceIter<..>; this is more flexible and lets us make the SliceChooseIter type private (or replace with a map), but I'm not sure we need that extra flexibility. This also requires us to bump the MSRV from 1.56 to 1.65.

[vks]

Can we return impl Iterator in traits?

[dhardy]

@vks no. I think this is one of Niko Matsaksis's goals, but it's not possible yet.

[LikeLakers2]

@dhardy I'm unsure why you would need GATs for your second suggestion. If the intent is to add an associated type that translates to an Iterator, you can do that without GATs - look at how IntoIterator is defined, for example:

pub trait IntoIterator {
    type Item;

    type IntoIter: Iterator<Item = Self::Item>;

    fn into_iter(self) -> Self::IntoIter;
}

That all said, I can't help but feel SliceRandom would need a rework (perhaps not a complete overhaul, though) to support cases like mine. I feel like trying to fit that support into what's currently available would make it hard - or at the very least, awkward - to work with. (Though it's worth mentioning that I'm only going off a feeling - if you can make it work well, by all means go ahead!)

[dhardy]

@LikeLakers2 I think you're right; it doesn't need GATs. Lets go back to your original motivation:

I'm trying to implement rand::seq::SliceRandom for a custom Vec-like collection I'm building.

SliceRandom is not implemented for Vec, only for [T]. I'm guessing your container does not implement Deref<Target=[T]>? E.g. to implement this trait for VecDeque would need some redesign. SliceRandom has two types of method:

• Choose something: these all produce one (or more) index, then return an element via that. These methods could be implemented over Index<usize>.
• Shuffle: the impls require a swap method, and partial_shuffle requires split_at_mut.

If we move the latter two methods to a separate trait we should be able to implement all the former for any Container: Index<usize>.

[LikeLakers2]

Sounds good to me! :) Shame that it can't be done without a breaking change, but hey, better now than past 1.x.

I'm guessing your container does not implement Deref<Target=[T]>?

Indeed it does not, as there's no good way (to my knowledge) to return a &[T] when needing to map values like that.

[dhardy]

Okay; we're already merging breaking changes so I think the plan should be something like this:

• Move all SliceRandom::choose* methods to a new trait named something like Indexed
• Implement Indexed for all T: std::ops::Index<usize>

Assuming that your container implements Index it will get the impl for free, as will VecDeque.

[LikeLakers2]

@dhardy

Assuming that your container implements Index it will get the impl for free, as will VecDeque.

How will Indexed know the highest usize it can request? Remember that Index will most likely panic if given a out-of-bounds index.

If I might suggest an alternative, perhaps Indexed could be implemented for all &T: IntoIterator (for example, Vec<T> implements IntoIterator for &Vec<T>), and would use IteratorRandom's methods to choose an item. That would still require the user to write an impl<T> IntoIterator for &T, but that's fairly easy where a collection already has a .iter() method - not to mention that it's not a rand-specific thing that needs to be implemented.

P.S. Lest you worry, this would not require consuming the container to turn it into an iterator: https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=a58d633964ef138956d804e28b15bf2e

[dhardy]

How will Indexed know the highest usize it can request?

Good point. The only standard trait providing a len method is ExactSizeIterator (unless I missed something).

The SliceRandom and IteratorRandom choose methods are not the same:

• IteratorRandom::choose is much more complicated than SliceRandom::choose. Though it should still be fast for anything with exactly known size, it will include much more code in any binary using it.
• SliceRandom::choose_multiple returns an iterator. IteratorRandom::choose_multiple cannot and allocates a Vec.
• IteratorRandom does not support weighted sampling.

So I don't like your proposal. An alternative might be to provide a trait like Indexed: Index<usize> with a len method (required) and choose methods (with default impls). You must implement this for your container, but only have to implement len (and Index) so it's easy to do so.

[LikeLakers2]

Ah, thank you for clarifying that. Admittedly, I've only taken a cursory glance at IteratorRandom, so I wasn't aware of those differences.

That sounds like a fine compromise to me! In the worst case, where a collection doesn't have an impl for Indexed, a user of that collection can still retrieve random elements - it's just a few more lines they'd have to write.

One last thing though: There are some choose_*() methods that return a mutable reference, which you would presumably need IndexMut<usize> for. I'd assume we'd be putting them in a separate IndexedMut trait?