Audit for missing `fold` implementations.

[jswrenn]

Implementing fold for our iterators allows us to provide more performant internal iteration. We provide it in some cases, but not all. I'd like us to take three steps towards resolving this:

1. Take an inventory of whether our adapters provide fold.
2. Implement fold for missing adapters.
3. (Potentially!) Implement a clippy lint to prevent regressions.

Happy to provide mentorship for any of these items.

[scottmcm]

Note that the vast majority of the time, you should be overriding fold, not for_each.

The default for_each just calls fold with a trivial () accumulator, which is easily optimized out (since in the default Rust calling convention, it's not even passed).

Thus the only reason to override for_each in addition to fold is if you can optimize something by knowing that the accumulation is stateless, but I can't off-hand recall any case where I've seen that to be the case.

[jswrenn]

Whoops, yes, of course. I'll modify the issue accordingly.

[Philippe-Cholet]

TODO list to track fold specializations (ordered by filepaths and line numbers)

• CoalesceBy
• MapSpecialCase
• Interleave
• InterleaveShortest
• PutBack
• Product
• TakeWhileRef: No test/benchmark yet.
• WhileSome
• TupleCombinations + Tuple1Combination + Tuple*Combination (macro)
• FilterOk
• FilterMapOk
• Positions
• Update
• MultiProduct: Might not be faster because of the heap-allocation bottleneck.
• Combinations: Might not be faster because of the heap-allocation bottleneck.
• CombinationsWithReplacement: Might not be faster because of the heap-allocation bottleneck.
• ConsTuples
• DuplicatesBy Implement DuplicatesBy::fold #921
• ExactlyOneError
• FlattenOk
• Groups: No test/benchmark yet.
• Group: No test/benchmark yet.
• Chunks: No test/benchmark yet.
• Chunk: No test/benchmark yet.
• IntersperseWith
• KMergeBy
• MergeBy
• MultiPeek
• PadUsing
• PeekingTakeWhile: No test/benchmark yet.
• PeekNth
• Permutations: Might not be faster because of the heap-allocation bottleneck.
• Powerset
• ProcessResults
• PutBackN
• RcIter: No test/benchmark yet.
• RepeatN
• TakeWhileInclusive
• Tee: No test/benchmark yet.
• TupleBuffer
• Tuples
• TupleWindows
• CircularTupleWindows
• UniqueBy Implement UniqueBy::fold #918
• Unique Implement Unique::fold #919
• WithPosition
• Zip
• ZipLongest

Should be ignored:

• deprecated: Unfold
• would not make sense: Iterate (infinite)!
• Default implementation is optimal:
  • Batching
  • ZipEq (see Do not implement ZipEq::fold (and change test) #915)

And rfold:

• MapSpecialCase
• Positions
• Update
• DuplicatesBy Implement DuplicatesBy::fold #921
• FlattenOk
• PadUsing
• RcIter: No test/benchmark yet.
• RepeatN
• UniqueBy Implement UniqueBy::fold #918
• Unique Implement Unique::fold #919
• Zip
• ZipLongest

I think we should mention this issue in related PRs to help maintain this big todo list.

[phimuemue]

Once we do this, we should test all of them via test_specializations.

[Owen-CH-Leung]

I'm interested to contribute to this crate and I digged a bit into the source code. I think one potential candidate to override fold is Combinations.

https://github.com/rust-itertools/itertools/blob/master/src/combinations.rs#L100

What do you guys think ?

I can create a PR in coming few days to implement this.

[phimuemue]

I'm interested to contribute to this crate and I digged a bit into the source code. I think one potential candidate to override fold is Combinations.

https://github.com/rust-itertools/itertools/blob/master/src/combinations.rs#L100

What do you guys think ?

I can create a PR in coming few days to implement this.

@Philippe-Cholet I think you're the most knowledgeable there. Could you mentor/review this?

[Philippe-Cholet]

I previously had some thoughts about spliting next in two methods to make a nth that would create only one vector instead of n+1 vectors. And I thought earlier it would be better done before fold but no as it needs to create each item anyway. I guess fold would be an interesting and total rewrite of next.
@Owen-CH-Leung Hi, sure you can help. And I'll be there to "mentor/review" it.