Tracking issue for iterator_fold_self

[KodrAus]

Tracking issue for Iterator::fold_first, like fold1 in Haskell.

Steps

• Initial implementation: Proposal: fold_self and try_fold_self for Iterators #65222
• Stabilisation PR: Rename Iterator::fold_first to reduce and stabilize it #79805

Open questions

• Naming.
• fold_first
• fold_with_first
• fold1
• reduce
• ...
• Should we reconsider try_fold_first?

[turion]

For me as a Haskeller who relatively new to Rust, try_fold_first sounds right, because it returns an Option.

[pcpenpal]

Following Scala's approach, what about reduce?

[Danue1]

Kotlin is doing the same naming.

https://kotlinlang.org/docs/reference/collection-aggregate.html#fold-and-reduce

[Riey]

I prefer reduce because it quite different from fold

fold compute acc with all elements then return acc type

but reduce compute all elements into one then return element type

[Kroisse]

reduce might be conflict with ParallelIterator::reduce in Rayon, which has the identity parameter act as fold's init parameter.

[WaffleLapkin]

Why only Iterator::fold_first was implemented and not DoubleEndedIterator::rfold_first? Is it appropriate to make a PR that adds the later method?

[rossmacarthur]

I think reduce is an appropriate name for this function. fold_with_first would also be better than fold_first.

[jagill]

This functionality is very useful for situations where there's no reasonable default value. For example, I'm using it for a parser, and would be very interested in it being stabilized.

I don't have a strong opinion on the name.

[amrhassan]

I concur, this would be very useful regardless of the name.

[jagill]

I'd like to officially push for stabilization. This feature is useful and available in many other languages, and the implementation is simple and non-controversial. The only debate so far is the name. I'll list the primary contenders for the name and the pros/cons I've read for each:

fold_first

The current name.

Pros:

1. It is the existing name that won't break anything.
2. It is similar to fold, so it is easy to remember, and the name gives a strong clue to what it does.

Cons:

1. It is, AFAICT, unique to Rust.

fold_with_first

[Edit: Added after suggestion]

Pros:

1. It is similar to fold, so it is easy to remember, and the name gives a strong clue to what it does.
2. It is more explicit than fold_first, so easier for first-time users.

Cons:

1. It is, AFAICT, unique to Rust.
2. It is longer than fold_first, and of similar utility to users who have used it a few times before.

reduce

Pros:

1. This would use fold and reduce the same way that Scala and Kotlin do, which may start an effective standardization.
2. The different names emphasize an important difference: while fold may have a different accumulator state, reduce returns the iterator Item type.

Cons:

1. For new people (not from Kotlin/Scala), it may seem arbitrary which functionality is fold and which is reduce.
2. It is not as obvious if you are looking at either fold or reduce that the other function exists.
3. It might conflict with ParallelIterator::reduce in Rayon.

try_fold_first

[Edit: Removed since most people disprefer this.]

Pros:

1. Emphasizes that it may return None, which is error-like.

Cons:

1. The current functions try_fold and try_for_each use try_ to indicate that the supplied function may fail. This function would use try_ to indicate that the fold may "fail" because the iterator is empty, not because the supplied function is fallible.

I'm happy to add additional pros/cons if people feel I've missed something important.

As stated before, I don't have strong feelings about the name. I weakly dislike try_fold_first, because it is using try_ differently than other functions within the group. In particular, the None case is not an error, but an expected result on an empty iterator.

[WaffleLapkin]

Personally, I'm against try_fold_first:

• try_ commonly corresponds to Result or T: Try, seeing it with Option is weird and confusing
• It's not an error actually, it's just an absence of value
• Similar function don't have try_ prefix, e.g.: find, position, max, etc
• too long :D

I'm also slightly in favour of reduce, partially because I've used Kotlin in the past, but also because it's nicer (?) and 1/first postfix didn't help me understanding semantics of the function...

[rossmacarthur]

Perhaps, something like fold_with_first is clearer as to the semantics of the function.

[kinnison]

I found myself wanting this last night. Based on the context in which I was using it, any of fold_first() reduce() or fold_with_first() would be good. I think try_fold_first() would have confused matters given it was in a function returning Result<>. My personal preference lies with fold_first() since my brain was hunting for fold1 already thanks to Haskell :D

[jagill]

Edited the summary post based on the comments above. I've removed try_fold_first, since all who have expressed an opinion (since the post) have disliked it for the same reason, which suggests that reason is strong. I've added fold_with_first as an option (heh), since it's more explicit than fold_first but has similar pros and cons.

To move things towards completion, I am now disprefering reduce, since fold/fold_{with_,}first are more explicit. It is not apparent from the names alone which version reduce is vs fold, while fold_{with_,}first is clearly the version that uses the first element. I weakly prefer fold_with_first, because it reads more nicely and is more obvious to someone just reading the name -- fold_first might be interpretable as just folding the first element. At least, when I first saw the name fold_first I had to read the description to know what it did.

[jagill]

Another argument against try_fold_first: I was folding an iterator that needed both the properties of try_fold (gracefully handling a fallible map) and fold_first (using the first item as the initial state, returning None if empty). This prospective fold function should have the name try_X, where X is the name of this stabilized feature.

[m-ou-se]

I personally prefer the name reduce, for the same reason as stated in #68125 (comment): Although related, fold and this function are fundamentally different. fold folds all the elements into a variable that could be of any type (e.g. it could be collecting integers into to a String), which doesn't have to be a reduction. reduce reduces the iterator to a single element (of the same type).

I don't think discoverability is a problem, as the documentation for fold can simply link to reduce and back, and the signature makes the difference very clear.

And as already mentioned above, we already have scan and fold with the same name as in Scala and Kotlin, and those languages also call this function reduce.

[WaffleLapkin]

I agree that the reduce is the best name so far, but there was a number of opinions, how do we decide?

[m-ou-se]

@WaffleLapkin I've already nominated this issue for the next libs meeting to make a decision on this. But looking at the 15 👍 and 0 👎 (currently at least) on the reduce suggestion, we could also just directly kick off an FCP on a stabilization PR that changes the name to reduce and see if everyone agrees. :)

[imjasonmiller]

I don't think discoverability is a problem

I have no experience with Kotlin or Scala, but coming from JavaScript, the name reduce is clear to me and I assume to many others as well. One of my first questions in the Rust Discord was about this method's functionality and how I'd achieve the same in Rust.

I've just used .fold_first() today and it's fantastic. Thank you. :-)

[felixc]

Ditto for Python, where it's called functools.reduce. So, to add another point of anecdata, that's the name I went looking for in the docs :)

[jagill]

reduce is the clear frontrunner. I support starting the FCP with reduce as the proposed name, and if there are strong objections they can be raised then (the C in FCP!). It'd be great to get the PRs merged before the next release cut.

[jacobchrismarsh]

Responding to this comment:

So instead we have to insert a cloned() into the iterator, which seems expensive:

Another solution to this would be to use into_iter as opposed to just iter to take ownership of the values.

I also stumbled onto this issue due to Advent of Code, and I'm a firm proponent of reduce. As mentioned above, that's the common terminology across several languages (scala, python, javascript, kotlin). This feature also matches the functionality in the aptly named "reduce" crate.

[m-ou-se]

(I'm a beginner!)

Welcome to Rust! :)

Would this also be the place to leave comments/questions on the API and usage?

It'd be better to ask quesitons like that on Discord or the users forum, to keep (tracking) issues like this focussed on the design of the API. Thanks!

[rossmacarthur]

@imjasonmiller #79805 (comment) brings up another concern for reduce() which I think hasn't been mentioned yet.

With Rust seemingly already having .rfold(), I think it might be hard on the eyes to possibly have .rreduce() — if that functionality might be added and the naming convention will be adhered to? In that regard, I think .rfold_first might be easier to read.

[jacobchrismarsh]

@rossmacarthur there's some more great discussion in that issue as well. It definitely flipped my opinion. While reduce is what my heart wants, it looks like fold and reduce are used pretty interchangeably in the world, and as such Rust should stick with fold and fold_first. Especially if rfold_first gets added to the API.

[rossmacarthur]

Yeah, it's also my concern that reduce seems to be quite an overloaded term. As for rfold_first / rfold_with_first, would it make more sense for it to be fold_last / fold_with_last 🤔 😅 ?

[rossmacarthur]

Also I think discoverability/familiarity is not really a concern. It would be very easy to make it so that reduce links to these functions in the documentation. This already works actually:

[leebenson]

FWIW, and this may be a minor point, but I like the fact that fold_first is right next to fold in the docs, alphabetically.

If this were reduce to fit other languages, it would have probably taken me a little longer to hunt down. I found the naming to be quite descriptive/instinctive, having it grouped with the explicit first value variant.

[old-mibmo]

Regardless of the name, this would be extremely useful.

I myself am partial to fold_first and fold_with_first, since they'd be right next to fold in the docs, like @leebenson mentioned.
fold1 would still be next to fold, but I'd be confused if I hadn't seen it before and encountered it in code.

[arnabanimesh]

I prefer fold_first because of the docs thing and also it shows that it is related to the fold function in some way. fold_with_first is unnecessarily verbose; reduce isn't descriptive, doesn't associate itself with fold and also it becomes confusing to memorize in the long run.

[m-ou-se]

@arnabanimesh See the stabilization PR for that discussion.

[jplatte]

Stabilized in #79805, this issue can be closed 🙂