Infinite `Iterator`s - on returning `Self::Item` instead of `Option<Self::Item>`


#1

I often wish we had an abstraction for talking about infinite Iterators in the std.

Whether I’m representing Signals in my DSP programming, generating Notes in my generative music software, or even just using std::iter::Repeat or Cycle I often find myself reaching for the Iterator trait with excitement, only to remember that I’m going to need to do lots of .unwrap()ing if I want to take advantage of its goodies. The goodies are very enticing and we all know them - those that come to mind include:

  • prelude availability
  • for loops!
  • zip
  • map
  • filter, filter_map
  • std::iter::repeat
  • itertools

However, the reality of course is that the API that I actually need just returns Self::Item and not Option<Self::Item>. What gives me slight pangs is that perhaps, in retrospect, we could have had an InfiniteIterator-like trait (perhaps with a far cooler name like Infinerator?) that could have had all these things. I can imagine a std::iter where we’d have something like this:

pub trait InfiniteIterator {
    type Item;
    fn next(&mut self) -> Self::Item;
    // fn map
    // fn zip
    // fn filter
    // fn filter_map
    // others?
}

impl<I> InfiniteIterator for I
    where I: Iterator,
{
    type Item = Option<<I as Iterator>::Item>;
    fn next(&mut self) -> Self::Item {
        Iterator::next(self)
    }
}

for loops would work with a hypothetical IntoInfiniteIterator, and would automatically break if the InfiniteIterator's associated Item type was Option<T> and returned None.

This is surely impossible now of course, as the stable train has long left the station! But I thought I’d share the retrospective while it was on my mind anyway and see if anyone else has come across the desire for an InfiniteIterator-like trait (and perhaps plant a seed for a future 2.0 consideration?!). It’s probably fine living in its own crate in the meantime, though this would miss half the goodies mentioned above.

mindtree glances longingly at the std::iter module of DoubleEndedIterators and ExactSizeIterators. He whispers in the ear of his lonely, hypothetical InfiniteIterator “maybe one day my prescious, maybe one day.”


#2
impl<I> InfiniteIterator for I where I: Iterator,

Shouldn’t it be impl<I> Iterator for I where I: InfiniteIterator?

would automatically break if the InfiniteIterator’s associated Item type was Option and returned None.

That would be very weird.

This is surely impossible now of course, as the stable train has long left the station!

What is preventing infinite iterators to be added to std? I don’t think adding new traits is a breaking change.

It’s probably fine living in its own crate in the meantime, though this would miss half the goodies mentioned above.

Most of the goodies you have mentioned are library features and can be reimplemented for infinite iterators. For the for loop it is necessary to convert infinite iterator to the usual one which requires one function call.


#3

I see what you mean. I think you should not be afraid to let them be their own thing and exist independently. None of the mentioned adaptors are simultaneously useful and convenient for both infinite iterators and iterators, they are better off with separate implementations.

  • An Iterator wrapper adapter gives you access to the for loop.
  • Potential absence of an element is everywhere present in iterator code, and an integral part of it.
  • An Iterator is not an infinite stream of Options, since you should stop calling .next() after the first None.

#4

FWIW an infinite iterator can be described as a generator that never returns, i.e. the final return type is ! so instead of specializing the concept of iterators, you could generalize to generators, which can also describe async fn / futures (in the readiness model), even without considering "expression yield" (the equivalent of Iterator::next taking a value).