New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Tracking issue for std::iter::from_fn #55977

Open
SimonSapin opened this Issue Nov 15, 2018 · 27 comments

Comments

Projects
None yet
9 participants
@SimonSapin
Copy link
Contributor

SimonSapin commented Nov 15, 2018

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

This comment has been minimized.

Copy link

jdahlstrom commented Nov 28, 2018

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

This comment has been minimized.

Copy link
Contributor Author

SimonSapin commented Nov 28, 2018

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

This comment has been minimized.

Copy link
Member

matklad commented Dec 13, 2018

@jdahlstrom there's already repeat_with for infinite iterators.

@matklad

This comment has been minimized.

Copy link
Member

matklad commented Dec 13, 2018

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 comment has been minimized.

Copy link
Contributor Author

SimonSapin commented Dec 13, 2018

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

This comment has been minimized.

Copy link
Member

alexcrichton commented Dec 18, 2018

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

This comment has been minimized.

Copy link
Contributor Author

SimonSapin commented Feb 1, 2019

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]);

@SimonSapin SimonSapin changed the title Tracking issue for std::iter::unfold and std::iter::successors Tracking issue for std::iter::unfold Feb 1, 2019

@matklad

This comment has been minimized.

Copy link
Member

matklad commented Feb 1, 2019

@SimonSapin should be move || { ?

@SimonSapin

This comment has been minimized.

Copy link
Contributor Author

SimonSapin commented Feb 1, 2019

Ah yes! Fixed, thanks.

@jdahlstrom

This comment has been minimized.

Copy link

jdahlstrom commented Feb 1, 2019

from_fn is very explicit and easy to understand. It makes clear that it's a constructor function making an iterator out of a function. +1.

@scottmcm

This comment has been minimized.

Copy link
Member

scottmcm commented Feb 1, 2019

I do feel strongly that something called unfold must have an explicit state (because fold does), but would be fine with either or both of unfold and from_fn.

@SimonSapin

This comment has been minimized.

Copy link
Contributor Author

SimonSapin commented Feb 1, 2019

@scottmcm I think this is a fair point, which is part of why I’m suggesting to rename :)

@SimonSapin

This comment has been minimized.

Copy link
Contributor Author

SimonSapin commented Feb 1, 2019

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

PR doing this: #58062

bors added a commit that referenced this issue Feb 2, 2019

Auto merge of #58062 - SimonSapin:iter_from_fn, r=alexcrichton
Rename iter::unfold to iter::from_fn and remove explicit state

This API is unstable.

CC #55977 (comment)

bors added a commit that referenced this issue Feb 2, 2019

Auto merge of #58062 - SimonSapin:iter_from_fn, r=alexcrichton
Rename iter::unfold to iter::from_fn and remove explicit state

This API is unstable.

CC #55977 (comment)

bors added a commit that referenced this issue Feb 3, 2019

Auto merge of #58062 - SimonSapin:iter_from_fn, r=alexcrichton
Rename iter::unfold to iter::from_fn and remove explicit state

This API is unstable.

CC #55977 (comment)

@SimonSapin SimonSapin changed the title Tracking issue for std::iter::unfold Tracking issue for std::iter::from_fn Feb 3, 2019

@SimonSapin

This comment has been minimized.

Copy link
Contributor Author

SimonSapin commented Feb 3, 2019

With that merged, I think the remaining questions are resolved. Though of course we can still bikeshed the new name.

@rfcbot fcp merge

@rfcbot

This comment has been minimized.

Copy link

rfcbot commented Feb 3, 2019

Team member @SimonSapin has proposed to merge this. The next step is review by the rest of the tagged team members:

No concerns currently listed.

Once a majority of reviewers approve (and none object), this will enter its final comment period. If you spot a major issue that hasn't been raised at any point in this process, please speak up!

See this document for info about what commands tagged team members can give me.

@rfcbot

This comment has been minimized.

Copy link

rfcbot commented Feb 5, 2019

🔔 This is now entering its final comment period, as per the review above. 🔔

@ErichDonGubler

This comment has been minimized.

Copy link

ErichDonGubler commented Feb 13, 2019

My only nitpick with calling this from_fn is that a closure is, indeed, not a function. If we were actually plugging in a fn item, there could be no state whatsoever!

This is a minor nitpick, but it does cause some cognitive dissonance for me and I worry it will do the same for people learning the language. Anybody have any thoughts or opinions on that?

@jdahlstrom

This comment has been minimized.

Copy link

jdahlstrom commented Feb 13, 2019

My only nitpick with calling this from_fn is that a closure is, indeed, not a function. If we were actually plugging in a fn item, there could be no state whatsoever!

The name should be mentally read "from Fn", but of course it can't literally be from_Fn due to naming conventions.

@SimonSapin

This comment has been minimized.

Copy link
Contributor Author

SimonSapin commented Feb 13, 2019

Indeed, the name is intended to refer to the Fn trait (and anything that implements it − modulo signature) rather than only fn functions or function pointers.

I’m open to another name though, if there are suggestions.

@ErichDonGubler

This comment has been minimized.

Copy link

ErichDonGubler commented Feb 13, 2019

Again a nitpick, but technically the bound is FnMut (a superset of Fn) and not Fn, right? It doesn't matter, I know -- I promise I'm trying to calm down the very OCD part of my brain about it. 😝


So, let me start this (larger than intended) comment by stating that I would be able to live with from_fn -- not that you need my permission. I'm hoping I can at least stimulate thoughts from others with some of my own in hopes we find something that makes everybody happy!

It's unfortunate we can't use unfold, since there's some prior art there. Like most functional terms, I don't think it's immediately and intuitively descriptive of what it does, but I found it acceptable. I don't particularly like conceptual alternatives to that, though:

  • unroll -- Maybe actually workable. Not sure it's intuitive, but unfold wasn't much better.
  • unravel -- I don't really want to "unravel" something in anybody's code!
  • unwind -- don't like the shared vocabulary this has with panic! semantics, this might be confusing without context.

I like the idea of from_<something>. Other monikers I can think of for the iterating function (IOW, what would replace <something>) would be:

  • fn_mut -- meh, this feels like it's trying too hard to be descriptive. This would also be problematic if the signature changed, though that's unlikely.
  • closure -- also feels descriptive in a mechanical way, but less bad than fn_mut with regards to tying the name to a type.
  • generator -- I don't know that it's a good idea to overlap this with the upcoming vocabulary for generators we intend to ship as part of the set of next major language features.
  • thunk -- this is very descriptive for somebody coming from a functional background. Not sure that we want to involve that jargon as its been absent from other std documentation that I know of, but maybe @Centril would appreciate it. :)
@Centril

This comment has been minimized.

Copy link
Contributor

Centril commented Feb 13, 2019

Naming aside, I think the design with the explicit state was better. In particular, it's ergonomic since a temporary let binding isn't required. Compare:

    match something {
        OtherVariant => { /* ... */ }
        SomeVariant => Box::new({
            let mut count = 0;
            std::iter::from_fn(move || {
                count += 1;

                if count < 6 {
                    Some(count)
                } else {
                    None
                }
            })
        }),
    }

    // vs.

    match something {
        OtherVariant => { /* ... */ }
        SomeVariant => Box::new(std::iter::from_fn(0, |count| {
            *count += 1;

            if *count < 6 {
                Some(*count)
            } else {
                None
            }
        })),
    }

The former encourages right-ward drift while the latter does not.

@matklad

This comment has been minimized.

Copy link
Member

matklad commented Feb 13, 2019

The problem is that you'll necessary have both the parameter and the closure, which is confusing. Like, even docs for unfold do not use explicit state.

If explicit state is more ergonomic in a particular instance, there's a high chance that successors from the neighbor issue will be more ergonomic still

    match something {
        OtherVariant => { /* ... */ }
        SomeVariant => Box::new(std::iter::successors(Some(1), |count| {
                Some(count + 1).filter(|it| it < 6)
        })),
    }
@Centril

This comment has been minimized.

Copy link
Contributor

Centril commented Feb 13, 2019

The problem is that you'll necessary have both the parameter and the closure, which is confusing. Like, even docs for unfold do not use explicit state.

But so does scan, and indeed also successors. If it is confusing, then it is at least consistently confusing.

@vi

This comment has been minimized.

Copy link
Contributor

vi commented Feb 14, 2019

Shall the word "unfold" be somewhere in docs for std::iter::from_fn (apart from unstable feature name), so that searching docs for "unfold" would find something?

Something like "similar function was previously called unfold" or "in functional programming, such operation is typically called unfold"?

@SimonSapin

This comment has been minimized.

Copy link
Contributor Author

SimonSapin commented Feb 14, 2019

It’s not quite the same as unfold though, in the variation without explicit state. And even with explicit state, there’s mutation through &mut S v.s. creating/moving a new S as part of the return value.

@vi

This comment has been minimized.

Copy link
Contributor

vi commented Feb 14, 2019

But previous unfold also used mutable state.

The same or not the same, the function is unfold-esque, so is relevant for searchs for the world "unfold".

@rfcbot

This comment has been minimized.

Copy link

rfcbot commented Feb 15, 2019

The final comment period, with a disposition to merge, as per the review above, is now complete.

SimonSapin added a commit to SimonSapin/rust that referenced this issue Feb 19, 2019

kennytm added a commit to kennytm/rust that referenced this issue Feb 19, 2019

kennytm added a commit to kennytm/rust that referenced this issue Feb 20, 2019

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment