Brainstorming: allowing implementing just `try_fold`, and getting `next` free

[scottmcm]

As we override more and more try_fold implementations on iterators, I’ve been thinking that .next() can always be implemented as x.try_for_each(Err).err() (or .find(|_| true), or a variety of other equivalent things), so long as try_fold has been overridden. And it looks like it’s pretty often optimal. Once the paths are folded, things like Chain look pretty much the same between the two.

So it’d be nice to let people not have to provide an implementation for next if they have one for try_fold.

Any thoughts on a nice way to allow that to work? I assume it’ll need language support, since just overriding both is a stack overflow hazard.

[sanxiyn]

Yes, this sounds great. I think this is called “minimal complete definition” in Haskell, and is suppored by GHC compiler using {-# MINIMAL #-}. I think we can mostly copy the design.

GHC MINIMAL pragma is documented in GHC Users Gude 9.31.5.

[Centril]

Supporting this in some form seems like a good idea.

Taking inspiration from {-# MINIMAL .. #-} and from our #[cfg(..)] construct, a sketch could be:

#[minimal(eq, ne)]
pub trait PartialEq<Rhs: ?Sized = Self> {
    fn eq(&self, other: &Rhs) -> bool { !self.ne(other) }
    fn ne(&self, other: &Rhs) -> bool { !self.eq(other) }
}

The list inside #[minimal(..)] constitutes a disjunction.

Like with #[cfg(..)], we can also use any(..) to embed a disjunction anywhere we want. all(..) can be used to require a conjunction of items. Optionally, not(..) could also be supported but that requires deeper thinking wrt. semantics when combined with specialization.

[dhm]

@scottmcm

just overriding both is a stack overflow hazard

If it is possible to lint the lack of explicit implementations for both next and try_fold (a lint that errors by default) that could be a great idea.

One way to maybe get it is by detecting (e.g. during monomorphization) that there exists an unconditional path from the beginning of f(...) into another f(...) call.

[steven099]

Seems like you could do this with default impls (if/whenever they’re supported). If someone implements TryFold (supplying the body of Iterator::try_fold as a static method), they get a default implementation of Iterator where Iterator::try_fold and Iterator::next are defined in terms of TryFold::try_fold.

[felix.s]

The #[minimal] syntax seems clunky. Maybe rather:

trait Foo {
    fn foo(&self);
    fn bar(&self);
    fn quux(&self);

    #[requires(foo,quux)]
    default fn bar(&self) {
        /* implement on top of foo and quux */
    }

    #[requires(bar)]
    default fn foo(&self) {
        /* implement on top of bar */
    }
}

Or even

trait Foo {
    fn foo(&self);
    fn bar(&self);
    fn quux(&self);

    #[requires(foo)]
    default {
        fn bar(&self) {
            /* implement on top of foo */
        }

        fn quux(&self) {
            /* implement on top of foo */
        }
    }
}

Of course, there’s the problem of what to do when we have

trait Foo {
    fn foo(&self);
    fn bar(&self);
    fn quux(&self);

    #[requires(foo)] default fn quux(&self) { /* ... */ }
    #[requires(bar)] default fn quux(&self) { /* ... */ }
}

impl Foo for Bar {
    fn foo(&self) {}
    fn bar(&self) {}
}

I guess in that case none of the default quux bodies should apply.

[dhm]

What about

trait Foo {
    fn foo(&self);
    fn bar(&self);
    fn quux(&self);

    #[requires(foo)]
    default fn quux(&self) { /* ... */ }
    #[requires(all(not(foo), bar))]
    default fn quux(&self) { /* ... */ }
}

impl Foo for Bar {
    fn foo(&self) {}
    fn bar(&self) {}
}