Internal iteration: try_fold vs try_for_each

Currently, Iterator::try_fold is the method to override to enable internal iteration, as virtually all iterator methods call it either directly or indirectly. Implementing it is usually quite straight-forward, but writing

acc = fold(acc, item)?;

all over the place can be a bit repetitive and keeping track of this state obfuscates the actual logic of the iteration.

I'm wondering if it's worthwhile to implement try_fold in terms of try_for_each instead of the other way around, making try_for_each the method one should override for internal iteration. Yielding an element is then simply done with

f(item)?;

and you'd no longer have to keep track of any iteration state other than the state specific to that particular iterator.

Implementing try_fold in terms of try_for_each is not as trivial as the other way around, unfortunately, because you can't move out of the iteration state from within the FnMut closure that is passed to try_for_each. Still, if I'm not mistaken, it's not too hard to work around this using raw pointers.

I'm hoping that this change will slightly lower the bar for people to implement internal iteration for their own iterators. Those who have implemented try_fold before, do you think it is worthwhile? Could this perhaps cause any issues that I haven't foreseen?

Using raw pointers to implement try_fold seems like code smell. Keeping track of the state isn't too bad anyways so I don't think that this is worth while. More over it is not trivial to implement try_fold in terms of try_for_each as you noted. This is not a small issue, especially when it is trivial to inplement try_for_each in terms of try_fold. Finally, this new way will likely not be as performant as the current version.

5 Likes

Totally, but it would only appear in core. Rust users wouldn't have to write this themselves. Introducing one code smell in core to make everyone's code a little cleaner seems like a worthwhile trade-off as far as code quality goes?

This would of course be a dealbreaker, but I have no reason to assume that this will impact performance in any way.

I view std (and core) as an example of good style for others, so code smell there is unacceptable.

Using raw pointers will make it harder for llvm to optimize, so it may drop performance. But instead of talking about it a, lets benchmark it. Do you have an implementation on hand?

1 Like

It would also simplify a lot of core::iter's code, and it would strictly improve the code of users. And to avoid an unsafe block inside Iterator::try_fold, a safe abstraction could be made. If the situation were reversed then you would have (rightly) complained that the change would add unnecessary noise to core::iter ¯\_(ツ)_/¯

Not yet, I'm working on it.

It seems weird to talk about this without also doing the same on fold and for_each. While I know that the default fold uses try_fold, stable folks can't name Try yet to override the latter, so they've only been writing the former.

Then you also have a migration problem. If you flip the dependency between (try_)fold and (try_)for_each, then folks who have overridden the folds will lose their optimization on for-each.

3 Likes

Another point of caution is that generic Try types don't get the benefits of #[must_use], so an iterator writing try_for_each with f(item)? might forget that ? with no warning. In try_fold, you have to maintain that generic and opaque accumulator, which pretty much forces you to do the right thing.

4 Likes

You would just use an Option to do that, not "raw pointers" (no idea how you would use "raw pointers" to do that safely).

The reason it's done this way is that precisely because try_fold is more general, so it doesn't seem to make any sense to do things the other way around, and also it can't be changed anyway due to backward compatibility.

This is just an implementation change so it is fine in terms of backwards compatibility

Thanks for bringing this up! This is a very valid concern, and something that can't be ignored. I suppose this doesn't break Rust's stability guarantees as existing code will continue to work, but yeah, it's still very much undesirable.

Ah, excellent point. I hadn't thought of this at all. I tried to come up with examples where try_for_each would prevent bugs and couldn't think of any, and now it seems it's the other way around :slight_smile: The accumulator (together with Rust's move semantics) indeed nicely forces you to not ignore the error. try_fold can still easily be implemented incorrectly, but I don't think try_for_each would prevent any of those bugs (I think true linear types might, though).

Why the quotation marks, am I using that term incorrectly? I'm not very experienced when it comes to unsafe Rust. I quickly hacked something together to check that all tests still passed based on how the take_mut crate is implemented, but I may not have done so correctly.

I would agree with you if all functions were pure, but since try_for_each takes an FnMut closure, I don't think try_fold is necessarily more general. The fact that try_fold can be implemented in terms of try_for_each demonstrates this. Hopefully it makes sense to you now :slight_smile:

Thanks for all the feedback! I think it's clear that this change isn't worthwhile.

6 Likes