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

#21

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
#22

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

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

1 Like
Std proposal: Option::fold()
#24

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
#25

To be clear, my lift is different from yours. There are quite a few different useful lifts for products of `Option`s. 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
#26

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
#27

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

#28

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
#29

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

1 Like
#31

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

closed #32

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