Introduce `iter::Either`?

[frewsxcv]

Has introducing the concept of Either to delegate to one of two iterators ever been discussed for inclusion in the standard library. So many crates I see either rely on a third party crate, or build in that behavior themselves, for what is pretty basic iterator functionality.

// PSEUDO IMPLEMENTATION

trait IteratorExt: Iterator {
    fn either<Other>(self) -> Either<Self, Other> {
        Either(EitherInner::First(self))
    }
}

struct Either<I, J>(
    // Hide the enum in this private field so we don't need to expose the variants
    EitherInner<I, J>,
)

enum EitherInner<I, J> {
    First(I),
    Second(J),
}

impl Iterator for Either {
    ...
}

// EXAMPLE

use std::iter;

// This or it could also return `impl Iterator<Item = i32>`
fn some_function() -> iter::Either<iter::Empty, iter::Once> {
    if whatever() {
        iter::empty().either()
    } else {
        iter::once(0i32).either()
    }
}

[cuviper]

That third-party crate either (which I co-maintain) does more than just Iterator -- why do you propose a more limited scope?

Even more generally, the auto_enums crate tries to solve this for quite a few types of impl Trait return values, with an arbitrary number of variants. I think that would be a more interesting feature to explore for the language proper, if we can do that type of delegation for arbitrary traits.

[frewsxcv]

I am proposing an iterator scope because that's the only usage of Either I've seen in the wild and that's the only usage of Either I've ever needed. I have a feeling the Left and Right names are subject to immense bikeshedding, and I don't think we need to expose those names this iter::Either API. We can just wrap the enum into a private struct field.

[CAD97]

The general feature is usually referred to as enum impl Trait (sometimes enum dyn Trait).

That said, this sort of delegation is quite complicated to generalize beyond specific traits; see the recent RFC#3367 for a discussion on that long tail. "Delegation safety" is related to dyn/object safety, except that presumably your impl Trait is Sized, so it also has any non-object-safe trait members guarded by where Self: Sized. ^[1]

Because of this, I could actually see std providing some sort of iter::Select combinator, as a kind of dual to iter::Chain. The interesting/difficult part is actually specifying what the stable interface should look like.

If you have a reasonably minimal API surface proposal, it'd be a reasonable fit for an ACP (basically a lighter weight RFC for pure library API additions). Here on IRLO is also a decent place to draft such.

Only .either() can't work, though: it only ever produces the "Either::Left" version. The minimal API surface will (modulo naming bikeshed) look something along the lines of

// mod ::core::iter

struct Select<A, B> { /* private fields */ }
impl<A, B> Iterator for Select<A, B>
where
    A: Iterator,
    B: Iterator<Item = <A as Iterator>::Item>,
{
    type Item = <A as Iterator>::Item;
    /* method implementation */
}
// plus other common traits; see Chain for a template

fn select_first<A, B>(a: A) -> Select<A, B>;
fn select_second<A, B>(b: B) -> Select<A, B>;

...although, now that I'm thinking about it, an alternative entry point could be

impl<T> Option<T> {
    fn unwrap_iter_or_else<U, F>(self, f: F) -> iter::Select<T, U>
    where F: FnOnce() -> U
    {
        match self {
            Some(a) => iter::select_first(a),
            None => iter::select_second(f()),
        }
    }
}

playing into the Flatten<Chain<Option<A>, Option<B>>> perspective, but naming that method is even harder, and any closure-based solution runs into the "mutex closure" problem where only one or the other can capture exclusive state, despite external knowledge only one closure will run, thus requiring the Option::take workaround to runtime encode that knowledge. So stick to the two separate constructors.

---

1. The design I feel most likely to happen falls under the enum dyn Trait camp; it behaves like Box<dyn Trait> and dereferences to &[mut] dyn Trait, but doesn't directly impl Trait itself unless the trait author defines that forwarding implementation themselves. The difference from Box being that it's (at least partially) monomorphized to the actual set of contained types, and as such can utilize enum dispatch instead of vtable dispatch, and doesn't require allocation. ↩︎

[SkiFire13]

@frewsxcv

fn some_function() -> iter::Either<iter::Empty, iter::Once> {
    if whatever() {
        iter::empty().either()
    } else {
        iter::once(0i32).either()
    }
}

This won't work, with the definition of either you gave the second branch will get type iter::Either<iter::Once<_>, _>, which is different than the type of the first branch (iter::Either<iter::Empty<i32>, _>)

[frewsxcv]

Wow I completely overlooked this. Okay this is really tricky to accomplish while retaining the ergonomics. I would like to avoid introducing separate methods for the left/right components, but it doesn't seem like there's any other way.

[scottmcm]

There could be some sort of iter_match! that wraps all the arms properly, but that's also something that could just be a crate.

@CAD97's mention of enum impl Trait is definitely what I'd like to see here, if we can ever get the details worked out.