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

Buried in the lengthy thread about catching functions is a use case by @scottmcm that maybe should be discussed independently:

which is a shorter way to write

``````fn add_opt(a: Option<i32>, b: Option<i32>) -> Option<i32> {
match (a, b) {
(Some(x), Some(y)) => Some(x+y),
_ => None
}
}
``````

I read that, and I thought, hey, isn't this a job for a lifting combinator? If it was a unary operation, we could write it that way already:

``````fn add_five(a: Option<i32>) -> Option<i32> { a.map(|x| x+5) }
``````

But we don't have combinators that let you write binary operations on `Option`s or `Result`s. Maybe we should.

2 Likes

You can use `and_then` for this I think?

``````fn add_opt(x: Option<i32>, y: Option<i32>) -> Option<i32> {
x.and_then(|x| y.map(|y| (x, y))).map(|(x, y)| x + y)
}
``````

I was contemplating suggesting `impl<T:Add<U>,U> Add<Option<U>> for Option<T>`, but unfortunately (IMHO) the fact that `Option` was made `Ord` prevents that from being done consistently for the comparison operators, so I don't know if it's a good idea for the other operators.

``````#![feature(unboxed_closures)]
#![feature(fn_traits)]

fn main() {
assert_eq!(f(Some(2), Some(3)), Some(5));

let g = OptionLift(std::ops::Neg::neg);
assert_eq!(g(Some(2)), Some(-2));
}

struct OptionLift<F>(F);

impl<F:FnOnce<(T0,)>,T0> FnOnce<(Option<T0>,)> for OptionLift<F> {
type Output = Option<F::Output>;
extern "rust-call" fn call_once(self, (a0,): (Option<T0>,)) -> Self::Output {
Some((self.0)(a0?))
}
}

impl<F:FnOnce<(T0,T1,)>,T0,T1> FnOnce<(Option<T0>,Option<T1>,)> for OptionLift<F> {
type Output = Option<F::Output>;
extern "rust-call" fn call_once(self, (a0,a1,): (Option<T0>,Option<T1>,)) -> Self::Output {
Some((self.0)(a0?,a1?))
}
}
``````
2 Likes

Hm, it could be simpler,

``````fn add_opt(x: Option<i32>, y: Option<i32>) -> Option<i32> {
x.and_then(|x| y.map(|y| x+y))
}
``````

There is a certain lack of motivation in this construct, though. I have to think about it to understand why the outer combinator must be `and_then` and the inner must be `map`. Not nearly so tidy as `¿{ x? + y? }`

2 Likes

Not nearly so tidy as ¿{ x? + y? }

If we aim for tidiness, I'd say that (currently working on stable) solution of `Ok(x? + y?)` is good enough.

5 Likes

Oh, neat, I did not know that already worked. (Modulo `Ok` versus `Some`.) Still haven’t fully grokked the expression-ness of the language.

I have the impression from the other thread that @scottmcm didn’t want to have to write `Some`, but I don’t think I would mind. `Ok(())` bugs me because I want to be able to fall off the end of a `-> Result<(),ErrorT>` function, not because of the typing.

That doesn't "capture" the errors, though, so only works if you want to use it in a method that returns an option where you want to return None if either is None.

Consider, for example, `Chain::size_hint`. The method doesn't return Option, so it can't use `?` without a catch block, but still wants to combine the two `Option<usize>` upper-bound hints. The actual working on stable solution is `(||{ Some(x? + y?) })()`, but I loathe that syntax. (Assuming inference cooperates, since it doesn't always with `?`-in-closures. And `Chain` needs `checked_add` to deal with overflow, but that's not important to the lifting discussion.)

Assuming a `Lift` like above, the problem is that, for example, `Lift(u32::max)` does something different from `Option<u32>::max`. (Both `max`s in this case being instances of `Ord::max`.)

a b Option::max(a, b) Lift(Ord::max)(a, b)
None None None None
Some None Some None
None Some Some None
Some Some Some Some

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.

If `Option` were only `PartialOrd` instead, `None` could be neither before nor after the `Some`s, which is less arcane than the current totally-arbitrary choice. (And `Option` wouldn't get a `min` from `Ord`, so we could choose how to define it, or even just to not define it at all. All arguments here are also true with `cmp::min`/`max`; that's just less clean to write in the tables.)

I don't want to have to write `¿{}` and `Some()`. One or the other is fine. I've elaborated on that in `catch` blocks are not `Ok`-wrapping their value · Issue #41414 · rust-lang/rust · GitHub

But what about just adding `Add` impls and so on? How is the current implementation of `Ord` for Option different from how the `Add` impls would be?

Well, the `Add` impl would be `Lift(Add::add)`. So things would be perfect if `PartialOrd` for `Option<T:Ord>` were just `Lift(Ord::cmp)`—since that’s even directly the correct `Option<Ordering>` type—but it’s not.

Compare some other languages, where `(None < Some) == false`, unlike Rust:

It certainly doesn’t prevent adding `Option<T:Add>: Add`, but I think it’d be a footgun for `Option<T>` to, for example, be almost identical to `diesel::sql_types::Nullable<T>`, the only difference being in a subset of the comparisons, like `None < Some` or `Some > None`. With no operators lifted the comparison behaviour is a quirk of `Option`; with all operators lifted except the comparison ones, it feels more like a trap.

The comments about `Lift` seem like a misdirection: the real question is what should `None + Some(_)` return? (Thinking in terms of “lift” suggests a particular answer, but the question is whether or not we should.) I don’t know if we have a clear answer; I agree with you that `None < Some(_) == true` suggests intuitively that `None + Some(x) = Some(x)`, but its not at all obvious thats the answer people want.

2 Likes

I think the biggest motivation for the `Lift` interpretation is heterogeneous operators.

Having `None + Some(x) => Some(x)` only naturally allows `Option<T:Add<Output=T>>: Add<Output=Option<T>>`. Allowing the most general `Option<T:Add<U>>: Add<Option<U>>` needs the `None + Some(x) => None` definition. The other definition would be possible with some extra bounds, maybe `T: Into<T::Output>, U: Into<T::Output>`, but that feels, subjectively, rather weird to me.

(So I think I agree with your last sentence, and I think I’m arguing the contrapositive: that people don’t want that `+` definition, so the `<` definition isn’t what they want either.)

I did not intend to suggest that we add implicit lifting of binary operations via `impl Add` and the like. I thought I was suggesting explicit binary lifters, along the lines of

``````fn add_opt(a: Option<i32>, b: Option<i32>) -> Option<i32> {
(a, b).map_both(|a, b| a+b)
}
``````

I’m not sure that’s better than `Some(a? + b?)` though.

No, C++ does this even worse than rust.

``````#include <optional>
#include <iostream>

int main(int argc, char **argv) {
std::optional<int> a = std::nullopt;
std::optional<int> b = 4;

std::cout << "None < Some(4): " << (a < b) << std::endl;
std::cout << "None > Some(4): " << (a > b) << std::endl;
std::cout << "Some(4) < None: " << (b < a) << std::endl;
std::cout << "Some(4) > None: " << (b > a) << std::endl;

std::cout << std::endl;
std::cout << "And you can even compare optional<int> to int..." << std::endl;
std::cout << "      None < 4: " << (a < 4) << std::endl;
std::cout << "      None > 4: " << (a > 4) << std::endl;
std::cout << "      4 < None: " << (4 < a) << std::endl;
std::cout << "      4 > None: " << (4 > a) << std::endl;
}
``````
``````None < Some(4): 1
None > Some(4): 0
Some(4) < None: 0
Some(4) > None: 1

And you can even compare optional<int> to int...
None < 4: 1
None > 4: 0
4 < None: 0
4 > None: 1
``````

That might work under a `MonadPlus` interpretation where `+` is seen as `<|>` (alternative), but under the `(+) <\$> Nothing <*> Just x == Nothing` interpretation (applicative lifting), which I find most intuitive, it does not work.

@scottmcm

I'd like to add that I find that Rust follows Haskell in doing the reasonable thing, that is: nothing is smaller than something.

1 Like

Did Haskell find some math to justify why `Nothing < Just _` (as opposed to `>`), or is it just an arbitrary choice that someone made once and now people follow?

This is a hilarious sentence, since something is smaller than `Just`: `Nothing`

1 Like

So I went and asked on #haskell @ freenode, and I got the following reply (verbatim.. I kid you not):

because nothing is less than anything

I asked about laws, but no one suggested any, so I think this was the rationale really.

Hmm… In various contexts you sometimes see this ‘first principles’ encoding of the natural numbers:

``````data Nat = Zero | Succ Nat
``````

…which would be isomorphic to

``````type Nat = Maybe Nat
``````

if that were valid - which it isn’t because type aliases can’t be recursive, but you get the idea.

So 0 would be represented by `Nothing`, 1 by `Just Nothing`, 2 by `Just Just Nothing`, etc.

Then at least in this special case, there’s a good reason for Nothing to compare as less than Just.

2 Likes

In actual Rust it would be more like `struct Nat(Option<Box<Nat>>)`, but yes, it does make sense in a way that `None < Some(_)`.

1 Like

My biggest concerns about this are twofold. First, the endless possibility of errors this can introduce. I have seen several bugs in my own code being prevented at compile time because (e.g.) two `Option<usize>`s or an `Option<i32>` and an `i32` didn’t `Add`. Sure enough, in most of the cases handling a missing value required special logic which I would have erroneously omitted if the compiler hadn’t slapped on my wrist.

And this immediately leads to my second concern. It’s not at all obvious what these operations should yield. One choice is the monadic-style "if either operand is `None`, the result is also `None`". Another possibility that I’ve seen suggested somewhere in this thread is “treat `None` as the identity element”, i.e. "the result is `None` only if both operands are `None`". Both interpretations may be useful in different scenarios, along with a variety of others.

For these two reasons 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. Neither one is clearly a natural `+` (etc.) operation on optionals, so code clarity would benefit more from a descriptively-named 2-ary free function that one would implement for oneself and that is specific to the problem being solved, instead of a single, rather ad-hoc choice of semantics for otherwise obviously-working operators being forced upon the entire ecosystem.

4 Likes