Add Default impls for iterators and adapters

[the8472]

Proposal

Problem statement

Currently many iterators don't implement Default which means one can't derive(Default) structs containing them, mem::take() or Cell::take them.

Motivation, use-cases

https://github.com/rust-lang/rust/blob/dc2d232c7485c60dd856f8b9aee83426492d4661/library/alloc/src/vec/drain.rs#L129

        let iter = mem::replace(&mut self.iter, (&mut []).iter());

could be replaced with

        let iter = mem::take(&mut self.iter);

Solution sketches

Iterator sources should implement Default when it is unambiguous that the default should be an empty iterator. Examples:

• slice::Iter{Mut}
• vec::IntoIter
• iter::Empty (already implements it)
• btree_map::Iter
• etc.

Adapters should implement it when the inner iterator does and when they don't have any closure that would have to be materialized

• Skip<I> where I: Default
• Flatten<I> where I: Default
• Chain<A, B> where A: Default, B: Default

Examples where it should not be implemented

• array::IntoIter since one could expect [T; N]::default().into_iter() where T: Default
• iter::Once since one could expect iter::once(Default::default())
• adapters::Map since it would require summoning an FnMut ex nihilo

Links and related work

• zulip discussion
• PR implementing Default for iter::Empty

What happens now?

This issue is part of the libs-api team API change proposal process. Once this issue is filed the libs-api team will review open proposals in its weekly meeting. You should receive feedback within a week or two.

[scottmcm]

Iterator sources should [...]

That sounds to me like this should perhaps be an RFC, since it substantially effects ecosystem crates too. (For example, https://docs.rs/ndarray/latest/ndarray/iter/struct.ExactChunksIterMut.html and https://docs.rs/itertools/latest/itertools/structs/struct.TupleWindows.html don't implement Default today, so accepting this is a de-facto "please send PRs adding Default to all these crates".)

But we'll see what libs-api says.

[the8472]

so accepting this is a de-facto "please send PRs adding Default to all these crates".

Eh. The "should" is more a recommendation to improve ergonomics, not as a requirement. Just as one "should" implement a size_hint better than the default if possible, but the TupleWindows you linked does not for example. Not every crate has to meet std's QoI standards, the "should" was meant for std.

[yaahc]

This one's insta-stable (right?) so it will need an FCP but my preliminary reaction is that this seems like a good idea.

Seconded

[jdahlstrom]

I think the general rule of thumb should be that if an iterator type has a reasonable invariant of yielding at least a single element, its Default, if any, must not be empty. Ie. any array::IntoIter<_; N> instance must yield exactly N items; Repeat must never yield None, and transitively for adapters.

[the8472]

Imo that's just one possible interpretation what Default would mean for array::IntoIter. Another possible meaning is to return an empty one. Due to that ambiguity I wouldn't implement it on those.

[jdahlstrom]

Yes, I agree that it's better to leave it unimplemented if there's any ambiguity. I just meant that IMHO it's better to not impl Default at all, rather than to impl an empty Default, for any iterator type whose "normal" constructor has an (explicit or implicit) postcondition on how many items it yields before None.

[the8472]

Has been implemented