iterator_item icon indicating copy to clipboard operation
iterator_item copied to clipboard

An alternative: just use FnMut

Open CAD97 opened this issue 3 years ago • 0 comments

This issue is primarily meant to log the semantic alternative I prefer. As it revolves around syntax to make fn() -> impl FnMut() -> Option<T> rather than fn() -> impl Iterator<Item=T>, it doesn't quite seem correct to implement it as a macro sketch here.

Full text: https://internals.rust-lang.org/t/rust-generators-exploration-of-potential-syntax/15586/8?u=cad97

It could look like:

fn merge_overlapping_intervals(input: impl Iterator<Interval>) -> impl Iterator<Item = Interval> {
    //         !1              !2
    std::iter::from_fn(move || loop {
        //                        !3
        let mut prev = input.next()?;
        for i in input {
            if prev.overlaps(&i) {
                prev = prev.merge(&i);
            } else {
                yield Some(prev); // !4
                prev = i;
            }
        }
        yield Some(prev); // !4
        yield None;       // !5
    });
}

Notes:

  1. Our semicoroutine just produces impl FnMut() -> Option<Interval>. To turn this into an iterator, we use iter::from_fn.
  2. We wrap the body in a loop. This is for convenience: otherwise, the implicit tail expression would return a (), which is not Option<Interval>, leading to a type error. As loop evaluates to type !, this coerces to our closure's return type just fine. Alternatively, we could have written the last line as a tail None. Note that return None; would not work[4], as we would still have the implicit tail expression returning () after it.
  3. ? works here. As our closure returns Option<Interval>, ? just works as normal. If input.next() yields a None, we resume from the top of the function the next time the closure is called.
  4. We yield Some(interval) here, because this is a -> Option<Interval> closure.[5] Through from_fn, this fills the Iterator contract of returning items via Some(interval).
  5. We yield None to indicate the end of the iterator stream. If and only if input is fused, we could instead leave this off, looping back to the start of the closure, and input.next()? would yield None; however, because we don't require input to be fused, we have to yield it ourselves to ensure None is yielded before calling next on the input iterator again. It also just helps with code clarity to do so explicitly. This could also be written as a tail-return None rather than the closure being a big loop (see point 2).

A more limited stabilization would avoid yield closures and instead only allow yield fn:

yield fn merge_overlapping_intervals(input: impl Iterator<Interval>) -> Option<Interval> {
    let mut prev = input.next()?;
    for i in input {
        if prev.overlaps(&i) {
            prev = prev.merge(&i);
        } else {
            yield Some(prev);
            prev = i;
        }
    }
    yield Some(prev);
    None
}

See the linked irlo post (practically a blog post) for more context into why I think this model is a good model.

CAD97 avatar Nov 15 '21 05:11 CAD97