Tracking issue for std::iter::from_fn

[SimonSapin]

Update: API modified in #58062:

pub fn from_fn<T, F>(f: F) -> FromFn<F> where F: FnMut() -> Option<T> {…}

#[derive(Clone)] pub struct FromFn<F> {…}

impl<T, F> Iterator for FromFn<F> where F: FnMut() -> Option<T> {
    type Item = T;
}

impl<St: fmt::Debug, F> fmt::Debug for FromFn<F> {…}

---

This API is being proposed in #55869:

pub fn unfold<St, T, F>(initial_state: St, f: F) -> Unfold<St, F>
    where F: FnMut(&mut St) -> Option<T> {…}

#[derive(Clone)] pub struct Unfold<St, F> {…}

impl<St, T, F> Iterator for Unfold<St, F> where F: FnMut(&mut St) -> Option<T> {
    type Item = T;
}

impl<St: fmt::Debug, F> fmt::Debug for Unfold<St, F> {…}

unfold was previously in the standard library but was deprecated and then removed in Rust 1.3 for not having “gained enough traction to retain its position in the standard library”. It is now available in the itertools crate.

My personal opinion is that we’ve been very conservative with inclusion in std in the months before and after 1.0 but we’ve slowing been relaxing the criteria, with in increasing number of small convenience functions and methods. Both unfold and successors feel general-purpose and fundamental enough to me to belong in the standard library.

Unresolved questions:

• Should the state field of Unfold be public?

• Should unfold have explicit state for consistency with fold, or should it be a more trivial bridging of closures to iterators with state kept in the closure’s environment or captures?

  impl<T, F> Iterator for Unfold<F> where F: FnMut() -> Option<T> {
      type Item = T;
      fn next(&mut self) -> Option<T> { (self.0)() }
  }

---

Update: moved to Moved to #58045:

pub fn successors<T, F>(first: Option<T>, succ: F) -> Successors<T, F>
    where F: FnMut(&T) -> Option<T> {…}

#[derive(Clone)] pub struct Successors<T, F> {…}

impl<T, F> Iterator for Successors<T, F> where F: FnMut(&T) -> Option<T> {
    type Item = T;
}

impl<T, F> FusedIterator for Successors<T, F> where F: FnMut(&T) -> Option<T> {}

impl<T: fmt::Debug, F> fmt::Debug for Successors<T, F> {…}

[jdahlstrom]

Some thoughts:

At least Haskell, Java, Scala, and itertools call the successors function iterate, with the distinction that they always return infinite sequences. The name iterate might sound very generic at first, but it makes sense seeing that it models the concept of iterated functions or iterative methods in mathematics.

successors takes an Option-returning function, closely mirroring the semantics of Iterator::next. In many (most?) use cases, the semantics could be emulated with an infinite-sequence-returning iterate combined with take or takeWhile. On the other hand, there are probably cases where it makes more sense for the function itself to decide when to stop. And typing an extra Some() is not a big deal when you do want an infinite iterator.

[SimonSapin]

with the distinction that they always return infinite sequences

That is in my opinion just not the same function. (And it’s a less useful one.)

closely mirroring the semantics of Iterator::next

Yes, this is the point: bridging closures to iterators in (almost, if explicit state is kept) the simplest possible way.

In many (most?) use cases, the semantics could be emulated with an infinite-sequence-returning iterate combined with take or takeWhile

This is a really convoluted work-around. I’d write a custom iterator type before coming up with it. And it requires a "sentinel" value that indicates end of iteration. If the iterated type doesn’t have such an unused value available, you’d have to make an infinite iterator of Option, then use takeWhile, then use map to unwrap those options.

[matklad]

@jdahlstrom there's already repeat_with for infinite iterators.

[matklad]

If we pick unfold without explicit state (my personal preference), then perhaps we can change it's name to align with repeat and repeat_with? unfold is very jargony, and repat_with has almost the same signature. A candidate name would be repeat_while.

[SimonSapin]

This API is not about repetition any more than any iterator is intended to be used by repeatedly calling .next(). (And I think that repeat_with is also not a good name.)

[alexcrichton]

We discussed this awhile back in a libs triage meeting and I've been meaning to post an update here as well!

It was sort of up in the air about an explicit state vs implicit-state-via-closure parameter. I know I still personally feel that this probably doesn't need an explicit state parameter on unfold, but there wasn't a clear majority!

In terms of naming it was pointed out that this is similar in functionality to repeat_with (for naming inspiration perhaps) and other possible candidates could be repeat_while (as @matklad mentioned as well as iter_fn used in the futures crate for a similar functionality.

In any case, just some thoughts!

[SimonSapin]

How about removing the explicit state and renaming to iter::from_fn?

let mut count = 0;
let counter = std::iter::from_fn(move || {
    count += 1;

    if count < 6 {
        Some(count)
    } else {
        None
    }
});
assert_eq!(counter.collect::<Vec<_>>(), &[1, 2, 3, 4, 5]);