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

[zackw]

I don’t think it would be a good idea to hard-wire either interpretation into the stdlib and let implicit magic happen — it is more confusing than helpful.

Yeah, again, it was never my intention to suggest that anything should happen implicitly. I only meant to suggest that maybe the stdlib should have explicit binary combinators, see above.

[H2CO3]

Oh, sorry, you’re right, I missed that part.

[fweimer]

And min doesn’t have this difference, so the solutions to nearly-identical problems turn out to be very different depending whether you’re looking for min or max, which can be quite confusing.

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 the expected lift from a semigroup T into a monoid T ⊍ {None}. But it is curiously absent from Haskell, Standard ML, and Java.

This is also the lift you need if you want to fold on a binary operation which does not have a natural zero element to start with, so the omission is even more curious.

[scottmcm]

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?

I don’t think such a lift can work in general. We’ve been talking about lifting Add::add and Ord::min, which are comparatively well-behaved. What would that kind of lift even mean for LiftB(Div::div), though? Having None / Some(4) => Some(4) seems like it’d always be wrong.

[fweimer]

To be clear, my lift is different from yours. There are quite a few different useful lifts for products of Options. I think the semigroup-to-monoid lift is useful in some contexts (e.g., folds without a natural start element), which is why I’m curious why it is generally underrepresented.

[scottmcm]

I understand you were talking about a different lift; I edited my previous post to try to make that clearer.

I’m curious why it is generally underrepresented

I think the answer is just that it’s hard to extend.

For example, the lift I’d defined extends obviously to a ternary function: the only way to get Some from a Lift(f32::mul_add) is to pass Some to all three arguments. But how would a LiftB(f32::mul_add) work, particularly if I passed exactly 2 arguments? There’s no obvious way to pick which to return, but nor is there a way to call the underlying function since you only have two arguments.

Similarly, the Lift defined above supports heterogeneous methods just fine. But how would you define LiftB(i16::rotate_left)? If done manually you could consider a None on the RHS an identity, but in general there’s no way to know that. And LiftB(i16::rotate_left)(None, Some(4)) returning Some(4) is particularly weird, even if enough support-the-conversion bounds were added to make it pass typeck.

[ExpHP]

The lift defined by @fweimer is for semigroups. None of your counterexamples are semigroups. But in that same respect, you have a point; I wouldn’t really call it a “lift”, either. It’s much too restrictive compared to your typical higher order abstraction. Applicative and monadic lifts like your Lift are so powerful because they support arbitrary functions without restriction.

Drawing a page from Haskell, I might sketch @fweimer’s idea into something more like this:

/// Trait for an associative operation
trait Semigroup: Sized {
    fn then(self, other: Self) -> Self;
}

// Things that could impl Semigroup
struct Max<T>(T);
struct Min<T>(T);

fn semigroup_opt<G: Semigroup>(a: Option<G>, b: Option<G>) -> Option<G>
{ ... }

(modulo weeks of futzing around to give it nicer ergonomics around borrowed data.)

And the generalization to more entries would merely reduce an IntoIterator<Item=Option<G>> into an Option<G>. (though it could also simply be written as a flattening operation followed by some IntoIterator<Item=G> -> Option<G>)

[dhm]

Late to the discussion here, but I agree with @zackw’s suggestion: do not add implicit lifters, since, as @H2CO3 pointed out, a None value can be treated as an identity element (e.g. for a max() function consistent with Ord for Option) or an absorbing element (e.g. for a min() function consistent with Ord for Option).

Since the choice depends on the binary operation being lifted, the only solution that makes sense is having 2 different lifters/methods ; something like .map2_all(...) and .map2_any(...) (with a better naming).

It would behave as expected for Some(_), Some(_) and None, None cases, but would differ when handling mixed inputs (absorbing None for map2_all, and identity None for map2_any)

[marcianx]

Now that you mention it, perhaps simply (opt1, opt2).map(...) or [opt1, opt2].map(...) might be nice additions to the standard library.

[scottmcm]

[opt1, opt2].map(...) might be nice additions to the standard library.

I expect we’ll get things like that once const generics land. (The same way that Option has them in addition to its iterators having them.)