libcore: add defaults for empty iterators

[bergus]

I'm looking for a way to create empty iterators.

I have a few places in my application where I keep an iterator around as part of a data structure, and will advance that from time to time. After a few rounds, I will reset the iterator to start from the beginning again. (The iterator is supposed to point into the data structure, so I got some problems with implementing that design even though the data is never dropped, but let's ignore that here).
To initialise my structure, I want to create an empty iterator, i.e. one that has no elements left and will only yield None.

pub struct X;
pub struct Example {
   iterator: Once<X>
}
impl Example {
  pub fn reset(&mut self) {
    self.iterator = once(X);
  }
}

let mut e = Example {
  iterator: ??? // how to create a consumed Once?
};
e.iterator.next(); // should yield None
e.reset();
e.iterator.next(); // will yield Option(X)
e.iterator.next(); // will yield None

In this particular case, I can use option::IntoIter directly instead of Once and write

pub struct Example {
   iterator: option::IntoIter<X>
}
impl Example {
  pub fn reset(&mut self) {
    self.iterator = Some(X).into_iter();
  }
}
let mut e = Example {
  iterator: None.into_iter()
};

but that doesn't express my intent as well as using Once. Also, given that in my actual code the iterator type is generic, I would need an additional method get_init next to get_reset in my trait. I'd rather have my trait say that the iterator type needs to implement Default, and the default value should be an instance of the iterator that doesn't yield anything.

My suggestion: Have all builtin iterators implement Default.

For example,

impl<A> Default for Item<A> {
  #[inline]
  fn default() -> Item<A> { Item { opt: None } }
}
impl<A> Default for Iter<A> {
  fn default() -> Iter<A> { Iter { inner: default() } }
}
impl<A> Default for IterMut<A> {
  fn default() -> IterMut<A> { IterMut { inner: default() } }
}
impl<A> Default for IntoIter<A> {
  fn default() -> IntoIter<A> { IntoIter { inner: default() } }
}
impl<T> Default for Once<T> {
  fn default() -> Once<T> { Once { inner: default() } }
}
// (not sure whether all of these could simply be derived)

Does this need to go through the RFC process? Should I simply create a pull request?

[cuviper]

It seems rather weird to me that a default Once<T> would be empty, rather than containing a T::default(). Using option::IntoIter for your example makes a lot more sense to me.

For other iterator types that could naturally start empty, like slices, an empty default seems fine.

[cuviper]

You could also make the empty case explicit to work for any generic iterator, storing Option<I> in your struct and dealing with None, or using Either like:

pub struct Example<I: Iterator> {
    iterator: either::Either<I, std::iter::Empty<I::Item>>,
}

So you'd assign Either::Left(some_iterator) or Either::Right(iter::empty()). Either already implements Iterator if its left and right types do, so you can use example.iterator.next() directly.

[bergus]

@cuviper Thanks for the feedback!

It seems rather weird to me that a default Once<T> would be empty, rather than containing a T::default().

Hm, that's another possibility, but I did think of it in terms of its Option-based implementation, and the impl Default for Option<T> is None. Which imo makes sense - instead of implementing the default collections only over defaultable types, as a collection containing exactly one of those items, the default value should be the empty collection and exist regardless of the item type.

And for iterators the same argument holds. I'd value the consistency that the default for an iterator is always the empty iterator. Much better than having case-by-case defaults.
Still, if we don't get a default for Once I'd be happy to use option::IntoIter with an empty default.

You could also make the empty case explicit and storing Option<I> or Either<Emtpy, I> in your struct

Yeah, I thought of using Option, but this comes with an overhead that I'd like to avoid (right?). Memory is at a premium on microcontrollers :-) So I was looking to do it with the iterator type itself - every iterator (but infinite ones like Cycle or Repeat) should be able to represent the consumed state.

[steveklabnik]

Triage: no change

[Mark-Simulacrum]

I don't personally think that implementing Default is a good idea due to the lack of clarity as to exactly what that would return (empty, vs. filled with Default values, possibly more alternatives). I would rather we don't do this at all, or provide constructors for these adapter types that create the empty (consumed) variants of them.

I would also expect that for many, though perhaps not all, cases of the iterator adapters, they're not actually more expensive to put inside an Option due to having at least one niche somewhere within :)

[bergus]

@Mark-Simulacrum I still think that "empty" is the only sensible answer to "how many default values should it be filled with" (and in general the Default implementation for x::iter should be the iterator that iterates the Default value of x, be it a slice or an option or something else), but yes providing some empty constructors would be an acceptable solution as well, allowing me to implement my own trait as well.

Regarding wrapping the iterator in an Option, that would require me to always use option.iter().flatten() which doesn't appear as clean and would need to do two comparisons when testing for emptyness.

[Mark-Simulacrum]

I think making this proposal more concrete might help -- e.g., listing the specific types that you would like to allow creating in an "empty" fashion.