# Std proposal: Option::fold()

**URL:** <https://internals.rust-lang.org/t/std-proposal-option-fold/9328>\
**Category:** Uncategorized\
**Created:** [February 2, 2019, 12:50pm UTC](https://internals.rust-lang.org/t/std-proposal-option-fold/9328 "2019-02-02T12:50:04Z")\
**Posts on this page:** 10\
**Page:** 1

<div class="post-metadata">

**Author:** ![djc](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/djc/32/1592_2.png) [@djc](https://internals.rust-lang.org/u/djc)\
**Post date:** [February 2, 2019, 12:50pm UTC](https://internals.rust-lang.org/t/std-proposal-option-fold/9328/1 "2019-02-02T12:50:04Z")

</div>

This is probably too small for a full RFC, but wanted to get some feedback on this idea before working on a PR.

Here’s the more specific thing I needed this week:

```rust
fn min_opt<T: Ord>(x: Option<T>, y: Option<T>) -> Option<T> {
    match (x, y) {
        (Some(x), Some(y)) => Some(cmp::min(x, y)),
        (Some(x), _) => Some(x),
        (_, Some(y)) => Some(y),
        _ => None,
    }
}

```

In my mind, the more general use case here is having two `Option`s and wanting to combine them in some way into a new `Option` that will pick the non-`None` option if there is only one or take an `Fn` to combine the two values if both are `Some` (it’s also related to currently unstable `xor()` in that this is like the inclusive or operation).

So this could be defined as:

```rust
fn fold<F>(other: Option<T>, merge: F) -> Option<T> where F: Fn(T, T) -> T {
    match (x, y) {
        (Some(x), Some(y)) => Some(merge(x, y)),
        (Some(x), _) => Some(x),
        (_, Some(y)) => Some(y),
        _ => None,
    }
}

```

(I suppose there might be value in generalizing `merge` to return `Option` as well.)

Is this something others have needed as well? Have I missed some straightforward way of expressing this with the current combinators? Does something like this exist in other languages which have `Option`-like types?

---

<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 2, 2019, 4:34pm UTC](https://internals.rust-lang.org/t/std-proposal-option-fold/9328/2 "2019-02-02T16:34:07Z")

</div>

> [@djc](#):
>
> Does something like this exist in other languages which have `Option` -like types?

The closest thing that comes to mind is [`unionWith :: Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k a `](http://hackage.haskell.org/package/containers-0.6.0.1/docs/Data-Map-Strict.html#v:unionWith). I think naming based on `union`/`merge` + `with` is more apt than `fold`.

---

<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 2, 2019, 5:43pm UTC](https://internals.rust-lang.org/t/std-proposal-option-fold/9328/3 "2019-02-02T17:43:51Z")

</div>

Previous discussion:

> [@Lifting binary operations, e.g. T+T → Option\<T\> + Option\<T\>](https://internals.rust-lang.org/t/lifting-binary-operations-e-g-t-t-option-t-option-t/6618/23):
>
> Is there a simple way today to get the other kind lift, which turns a binary operation on T into a binary operation on Option\<T\>, respecting the new identity element None? fn lift\<T, F: FnOnce(T, T) -\> T\>( f: F, left: Option\<T\>, right: Option\<T\>) -\> Option\<T\> { match (left, right) { (None, right) =\> right, (left, None) =\> left, (Some(left), Some(right)) =\> Some(f(left, right)), } } This does the right thing for std::cmp::min, std::cmp::max. I think this is …

---

<div class="post-metadata">

**Author:** ![RReverser](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/rreverser/32/2189_2.png) [@RReverser](https://internals.rust-lang.org/u/RReverser)\
**Post date:** [February 2, 2019, 5:55pm UTC](https://internals.rust-lang.org/t/std-proposal-option-fold/9328/4 "2019-02-02T17:55:00Z")

</div>

> [@djc](#):
>
> Have I missed some straightforward way of expressing this with the current combinators?

The closest I can think of is `fold1` from `itertools` - while it's an external crate, it seems to be very close to what you want and could be used as:

```rust
fn fold<T>(x: Option<T>, y: Option<T>, merge: impl Fn(T, T) -> T) -> Option<T> {
    x.into_iter().chain(y).fold1(merge)
}

```

---

<div class="post-metadata">

**Author:** ![djc](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/djc/32/1592_2.png) [@djc](https://internals.rust-lang.org/u/djc)\
**Post date:** [February 2, 2019, 9:38pm UTC](https://internals.rust-lang.org/t/std-proposal-option-fold/9328/5 "2019-02-02T21:38:21Z")

</div>

> [@Centril](#):
>
> The closest thing that comes to mind is [`unionWith :: Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k a`](http://hackage.haskell.org/package/containers-0.6.0.1/docs/Data-Map-Strict.html#v:unionWith). I think naming based on `union` / `merge` + `with` is more apt than `fold` .

Ah yes, forgot to include a section on naming. Actually the first name I came up with was `combine()`, but since the idea seemed to bear some similarities to `Iterator::fold()`, I thought `fold()` might fit in better. `merge()` also seems like a decent option.

> [@scottmcm](#):
>
> Previous discussion:

My take away from that discussion is that they were trying to come up with a much more general API for applying binary operations to pairs of `Option`s, but that it was hard to find something to fit. In other words, it seems to be some proof of demand for this feature, and an indication that it might be at a right level of specificity compared to the attempts from that thread.

> [@RReverser](#):
>
> The closest I can think of is `fold1` from `itertools` - while it’s an external crate, it seems to be very close to what you want

That looks decent, but it seems like a pretty big dependency to pull in for this small thing.

---

<div class="post-metadata">

**Author:** ![RReverser](https://sea2.discourse-cdn.com/flex002/user_avatar/internals.rust-lang.org/rreverser/32/2189_2.png) [@RReverser](https://internals.rust-lang.org/u/RReverser)\
**Post date:** [February 3, 2019, 12:53am UTC](https://internals.rust-lang.org/t/std-proposal-option-fold/9328/6 "2019-02-03T00:53:43Z")

</div>

> [@djc](#):
>
> That looks decent, but it seems like a pretty big dependency to pull in for this small thing.

Yeah, sure, if you don't already have it, I think I'd go with handwritten match, just maybe simplified it a bit:

```rust
fn fold<T>(x: Option<T>, y: Option<T>, merge: impl Fn(T, T) -> T) -> Option<T> {
    match (x, y) {
        (Some(x), Some(y)) => Some(merge(x, y)),
        (x, y) => x.or(y),
    }
}

```

---

<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 3, 2019, 3:22am UTC](https://internals.rust-lang.org/t/std-proposal-option-fold/9328/7 "2019-02-03T03:22:37Z")

</div>

> [@djc](#):
>
> and an indication that it might be at a right level of specificity compared to the attempts from that thread.

The linked post in that thread is _exactly_ the monoidal lift you're talking about here. (I agree the broader points are looking at more generally-applicable lifts.)

> [@djc](#):
>
> it seems like a pretty big dependency to pull in for this small thing.

It's all generics, though, so it's low-weight. (It's not like it always links a big data file or something.) And it's already used by a bunch of other popular crates: [crates.io: Rust Package Registry](https://crates.io/crates/itertools/reverse_dependencies)

And you might not even need a method to wrap it, since it can be further simplified to

```rust
chain(x, y).fold1(merge)

```

Demo: [Rust Playground](https://play.rust-lang.org/?edition=2018&gist=02dbb1fbd06c57ed014633ff06453b41)

---

<div class="post-metadata">

**Author:** ![stijn-devriendt](https://avatars.discourse-cdn.com/v4/letter/s/c0e974/32.png) [@stijn-devriendt](https://internals.rust-lang.org/u/stijn-devriendt)\
**Post date:** [February 7, 2019, 8:27am UTC](https://internals.rust-lang.org/t/std-proposal-option-fold/9328/8 "2019-02-07T08:27:19Z")

</div>

In some OCaml code I’ve had the need for 2 similar functions. One goes like

```rust
val merge_any: 'a option -> 'a option -> ('a -> 'a -> 'a) -> 'a option

let merge_any left right f =
    match left, right with
    | Some l, Some r -> Some (f l r)
    | Some x, None
    | None, Some x -> Some x
    | None, None -> None

```

The other is like:

```rust
val merge_both: 'a option -> 'b option -> ('a -> 'b -> 'c) -> 'c option

let merge_both left right f =
   match left, right with
   | Some l, Some r -> Some (f l r)
   | _, _ -> None

```

The implementations are fairly simple, but finding an accurate name was the hardest part. I also looked through Haskell and Rust’s option types, but couldn’t find anything similar. Also mind the signatures, even though the implementations aren’t very different, the signatures are.

Takeway from me is: consider both functions at once before settling on a name.

---

<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 7, 2019, 5:42pm UTC](https://internals.rust-lang.org/t/std-proposal-option-fold/9328/9 "2019-02-07T17:42:03Z")

</div>

> [@stijn-devriendt](#):
>
> Takeway from me is: consider both functions at once before settling on a name.

Again, see the other thread. The first is a semigroup-to-monoid adapter, the latter is a proper extensible lift to the option monad.

---

<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 8, 2019, 5:45pm UTC](https://internals.rust-lang.org/t/std-proposal-option-fold/9328/10 "2019-05-08T17:45:32Z")

</div>

Closed on May 8, 2019, 5:45pm UTC

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