# Brainstorming: allowing implementing just \`try\_fold\`, and getting \`next\` free

**URL:** <https://internals.rust-lang.org/t/brainstorming-allowing-implementing-just-try-fold-and-getting-next-free/9417>\
**Category:** Uncategorized\
**Created:** [February 12, 2019, 2:06am UTC](https://internals.rust-lang.org/t/brainstorming-allowing-implementing-just-try-fold-and-getting-next-free/9417 "2019-02-12T02:06:04Z")\
**Posts on this page:** 8\
**Page:** 1

<div class="post-metadata">

**Author:** ![scottmcm](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/scottmcm/32/2355_2.png) [@scottmcm](https://internals.rust-lang.org/u/scottmcm)\
**Post date:** [February 12, 2019, 2:06am UTC](https://internals.rust-lang.org/t/brainstorming-allowing-implementing-just-try-fold-and-getting-next-free/9417/1 "2019-02-12T02:06:04Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![sanxiyn](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/sanxiyn/32/8824_2.png) [@sanxiyn](https://internals.rust-lang.org/u/sanxiyn)\
**Post date:** [February 12, 2019, 2:32am UTC](https://internals.rust-lang.org/t/brainstorming-allowing-implementing-just-try-fold-and-getting-next-free/9417/2 "2019-02-12T02:32:51Z")

</div>

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](https://ghc.readthedocs.io/) 9.31.5.

---

<div class="post-metadata">

**Author:** ![Centril](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/centril/32/3334_2.png) [@Centril](https://internals.rust-lang.org/u/Centril)\
**Post date:** [February 12, 2019, 2:48am UTC](https://internals.rust-lang.org/t/brainstorming-allowing-implementing-just-try-fold-and-getting-next-free/9417/3 "2019-02-12T02:48:56Z")

</div>

Supporting this in _some form_ seems like a good idea.

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

```rust
#[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.

---

<div class="post-metadata">

**Author:** ![dhm](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/dhm/32/4879_2.png) [@dhm](https://internals.rust-lang.org/u/dhm)\
**Post date:** [February 12, 2019, 3:51pm UTC](https://internals.rust-lang.org/t/brainstorming-allowing-implementing-just-try-fold-and-getting-next-free/9417/4 "2019-02-12T15:51:25Z")

</div>

> [@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](https://doc.rust-lang.org/rustc/lints/listing/warn-by-default.html#unconditional-recursion).

---

<div class="post-metadata">

**Author:** ![steven099](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/steven099/32/3871_2.png) [@steven099](https://internals.rust-lang.org/u/steven099)\
**Post date:** [February 13, 2019, 4:06am UTC](https://internals.rust-lang.org/t/brainstorming-allowing-implementing-just-try-fold-and-getting-next-free/9417/5 "2019-02-13T04:06:48Z")

</div>

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.

---

<div class="post-metadata">

**Author:** ![felix.s](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/felix.s/32/8073_2.png) [@felix.s](https://internals.rust-lang.org/u/felix.s)\
**Post date:** [February 13, 2019, 8:09am UTC](https://internals.rust-lang.org/t/brainstorming-allowing-implementing-just-try-fold-and-getting-next-free/9417/6 "2019-02-13T08:09:56Z")

</div>

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

```rust
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

```rust
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

```rust
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.

---

<div class="post-metadata">

**Author:** ![dhm](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/dhm/32/4879_2.png) [@dhm](https://internals.rust-lang.org/u/dhm)\
**Post date:** [February 13, 2019, 10:41am UTC](https://internals.rust-lang.org/t/brainstorming-allowing-implementing-just-try-fold-and-getting-next-free/9417/7 "2019-02-13T10:41:55Z")

</div>

What about

```rust
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) {}
}

```

---

<div class="post-metadata">

**Author:** ![system](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/system/32/14092_2.png) [@system](https://internals.rust-lang.org/u/system)\
**Post date:** [May 14, 2019, 10:41am UTC](https://internals.rust-lang.org/t/brainstorming-allowing-implementing-just-try-fold-and-getting-next-free/9417/8 "2019-05-14T10:41:56Z")

</div>

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.