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

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.

4 Likes

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

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.

2 Likes

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.

2 Likes

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.

1 Like

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

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.

2 Likes

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

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)

2 Likes

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

1 Like

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

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