Std proposal: Option::fold()

[djc]

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:

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 Options 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:

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?

[Centril]

@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 . I think naming based on union/merge + with is more apt than fold.

[scottmcm]

Previous discussion:

Lifting binary operations, e.g. T+T → Option<T> + Option<T>

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 …

[RReverser]

@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:

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

[djc]

@Centril

The closest thing that comes to mind is unionWith :: Ord k => (a -> a -> a) -> Map k a -> Map k a -> Map k a . 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 Options, 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.

[RReverser]

@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:

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),
    }
}

[scottmcm]

@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

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

chain(x, y).fold1(merge)

Demo: Rust Playground

[stijn-devriendt]

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

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:

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.

[scottmcm]

@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.