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

#11

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.

#12

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

#13

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.

#14

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

#15

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.

#16

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`

#17

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.

#18

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.

#19

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(_)`.

#20

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.

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

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

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.

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

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

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

#29

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

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