Can it be implemented bit by bit in Rust?

#1

I'm learning rust iterators and I was trying to implement this, as now C++ does it:
But I stumbled accross problem with skip in rust as it does not implement DoubleEnded Iterator so it cannot be passed to rev. Any ideas?

Screenshot from 2021-11-01 15-08-08
Screenshot from 2021-11-01 15-08-081022×460 110 KB

From:

#2

You can use .take(3) if you know how many elements to expect.

The Iterator trait itself doesn't implement this for .skip(2).rev(), because next() is theoretically allowed to stop at any time, so you don't know when it's two calls before the end.

Alternatively, skip(2).collect::<Vec<_>>().into_iter().rev() to buffer the items.

#3

I belive that the problem here is with skip. Why would skip not produced DoubleEnded iterator? I mean, logically thinking skip should produce same iterator as it operates on lessened by the number of elems. Isn't that logical thing to do?

#4

If you don't know the "length" of the iterator up front, you can't know whether DoubleEndedIterator::next_back should call next_back on the contained iterator or just return None, because you don't know if the skipped prefix covers the whole iterator or not.

1 Like
#5

I think you also need to know the number of elements, which you can't after filter.
I wonder how C++ does it without collecting first

#6

Yet, they do it "somehow" in C++...

#7

Surely, having skip returning DoubleEnded iterator would only mean that if there is something next_back can return it and if there isn't something then return None?
My point is that at high level of abstraction skip should not return different type of iterator than the one it operates on.

#8

If I had to guess, the C++ is doing some buffering behind the scenes, so the whole filter + transform + drop is computed eagerly before reverse runs. The analogous Rust combinators are lazy, so they can't take advantage of buffering.

#9

Is there a specific reason why skip cannot return same type of iterator as it is operating on?

#10

Let's be concrete: the problem is to write this impl

impl<I: DoubleEndedIterator> DoubleEndedIterator for std::iter::Skip<I> {
    fn next_back(&mut self) -> Option<Self::Item> {
        todo!()
    }
}

For reference, internally std::iter::Skip looks like

struct Skip<I> {
    iter: I,  // the wrapped iterator
    n: usize, // how many items need to be skipped
}

So, how should next_back be implemented? I think you'll find that there is no way to do it with just the DoubleEndedIterator interface and the data stored in Skip<I>; you need to know more about the contained iterator.

Incidentally, the Iterator impl for Skip<I> is basically

impl<I: Iterator> Iterator for Skip<I> {
    type Item = I::Item;

    fn next(&mut self) -> Option<Self::Item> {
        match self.n {
            0 => self.iter.next(),
            n => {
                self.n = 0;      // so we don't do the skip more than once
                self.iter.nth(n) // drops the first n items and returns the item after
            }
        }
    }
}
2 Likes
#11

The iterator returned by skip needs to remember how many items should be skipped, and in order to be able to store that information somewhere it has to be a custom type.

1 Like
#12

And how is DoubleEnded iterator implemented for take?

#13

It's only implemented for Take<I> when I: DoubleEndedIterator + ExactSizeIterator, i.e. the length is known.

#14

Which would mean that Skip could be done in exactly this same way. As Skip is the "opposite" of take.

#15

And it is done - the following code compiles (playground):

fn rev_skip<I>(iter: I) -> impl Iterator<Item = i32>
where
    I: Iterator<Item = i32> + DoubleEndedIterator + ExactSizeIterator,
{
    iter.skip(2).rev()
}

However, iterator created by filter obviously can't implement ExactSizeIterator, since the size of the filtered iterator is known only after the iteration is finished. And without ExactSizeIterator bound the code above would yield an error.

6 Likes
#16

But that is different to what I've said in response to @cole-miller.
If take can be implement for DoubleEndedIterator, so should skip be able. We not talking about rev_take.
My point is that when implementing the construction from my OP, I want to skip (not rev_skip) few elems and only then reverse the outcome.

#17

Without ExactSizeIterator, take().rev() cannot be used, too - playground.

#18

Then just shows that C++ does something better/more clever.

#19

More likely is that C++ has some implicit operations with unknown overhead. Or you can write an algorithm to do what you want imperatively without the intermediate buffering?

#20

I don't know - perhaps. But I still think that if take can be implemented for DoubleEnded so should be skip.