# max(x::T, y::T) and min must be commutative!

I could not believe it in julia Version 0.6.0 (2017-06-19 13:05 UTC) I got

``````julia> max(Set([1]), Set([2]))
Set([2])
julia> max(Set([2]), Set([1]))
Set([1])
julia> min(Set([1]), Set([2]))
Set([1])
julia> min(Set([2]), Set([1]))
Set([2])
``````

Now, `Set{T} where T` does not have a canonical total order but a canonical partial order. Julia is aware of the difference, as the doc of `<` includes:
`Types with a canonical partial order should implement <, and types with a canonical total order should implement isless.`

The implementation of of max (for non-numerical types) comes to `max(x,y) = ifelse(y<x, x, y)`. This is perfectly valid for total orders but wrong for partial orders, as in the case of `Set`.

So `max(x, y) = ifelse(isless(y,x), x, y)` seems more appropriate to me. It would result in:

``````julia> max(Set([1]), Set([2]))
ERROR: MethodError: no method matching isless(::Set{Int64}, ::Set{Int64})
Stacktrace:
[1] max(::Set{Int64}, ::Set{Int64}) at ./REPL[115]:1
[2] macro expansion at ./REPL.jl:97 [inlined]
[3] (::Base.REPL.##1#2{Base.REPL.REPLBackend})() at ./event.jl:73
``````

according to the imperative that it is better to obtain an error condition than to obtain an unreliable or arbitrary result.

In order to remove the Exception it would be possible to re-define the meaning of `max`. It should return the lowest upper bound, if it exists. For total orders and numerical types, that is equivalent to âthe maximal elementâ. For non-numeric types implementing â<â instead of `isless` the implementers should be encouraged to provide `max` and `min` to return âleast upper boundâ respectively âgreatest lower boundâ.

As far as I can see, in the Base package, only `Set` and `IntSet` are affected.
To following lines in `base/set.jl` would solve the requirement:

``````max(x::AbstractSet{T}, y::AbstractSet{T}) where T = union(x, y)
min(x::AbstractSet{T}, y::AbstractSet{T}) where T = intersect(x, y)
``````

as can be seen:

``````julia> min(Set([1]), Set([2]))
Set{Int64}()
julia> min(Set([2]), Set([1]))
Set{Int64}()
julia> max(Set([1]), Set([2]))
Set([2, 1])
julia> max(Set([2]), Set([1]))
Set([2, 1])
``````

Just out of interest, what result should you expect when taking the max of two sets?

The relevant code appears to be

``````<( l::Set, r::Set) = (length(l) < length(r)) && (l <= r)
<=(l::Set, r::Set) = issubset(l, r)
``````

and since `max` will return the second argument if `<` is false, itâs returning the second argument.

``````struct Foo
x::Int
y::Char
end

<(a::Foo, b::Foo) = a.x < b.x
==(a::Foo, b::Foo) = a.x == b.x

a = Foo(1, 'a')
b = Foo(2, 'b')
c = Foo(1, 'c')

a < b     # true
b < a     # false
a == c    # true
max(a, c) # Foo(1, 'c')
max(c, a) # Foo(1, 'a')
``````
1 Like

I would expect `max(s1,s2) == union(s1,s2)` and `min(s1,s2) = intersect(s1,s2)` for sets s1 and s2.
Actually max and min are not the correct names, if the order is partial, it should be `upperbound` or `supremum` resp. `lowerbound` or `infimum` instead, which would be the correct terms in order theory.
So my preferred solution would be to let `max(s1,s2)` throw an exception if s1, s2 are sets or do not define `isless` by any reason. At the same time I would define two of the proposed functions only for non-numericals, which do not define `isless`, but `<`.
The idea of re-using the names `max`, `min` was just for reasons of economy and name space pollution of the Base module.
There is a related discussion about âmaximum, minimum, mapreduce âŚâ, which goes the same direction.

This would turn `max` at least into an O(n) operation with no short-circuiting.

That is correct, `union(s1,s2)` and `intersect(s1,s2)` on sets are more expensive than `s1 < s2` on sets in general. If `length(s1) < length(s2)` or if both are `IntSet`, the effort is comparable.
I would never trade performance for usability of results.

What does the code example show? The wit of my original post was `max(a,b) != max(b,a)`, even if `a != b`. That means `max` applied to sets is not commutative.

My code was intended to show how one can define equality and not get obviously-commutative results from `max` (though I would argue that the results do show commutativity). I guess my point is this:

``````julia> Set([1]) < Set([2])
false

julia> Set([2]) < Set([1])
false

julia> Set([2]) == Set([1])
false

julia> Set([2]) < Set([1,2])
true
``````

so therefore `max` is not well-defined on `Set`s, at least as far as providing an intuitive answer. I think this is because weâve chosen to âoverloadâ `<` to provide a short-circuiting `issubset()`, and this gets generalized into what we see with `max`, which is defined generally as `max(x, y) = ifelse(y < x, x, y)`.

I agree that this definition of `max` has little obvious value to sets, but Iâm not sure we should special-case a method just to throw an error. Itâs not obvious to me why one would want to take the `max` of two sets in any case, and redefining `max` to be an alias of `union` is but one way of many to define `max` for a set.

I do not agree with your arguments.
What I wanted to explain, that the current implementation of max is not ok for types, which implement a partial order (by defining `<`). The implementation `max(x,y) = ifelse(y < x, x, y)` makes `max` commutative only for totally ordered types (which are implementing `isless`).

'max` should never be non-commutative. But it is currently.

In order to guarantee commutativity, the proposal of `max(x,y) = ifelse(isless(y,x), x, y)`.
If nothing else is changed, that throws an exception (`isless`is not defined) for the partially ordered types.

The second question is, if it is possible to assign a valid natural meaning to `max`.
That depends on the individual type. For `AbstractSet` that seems to me union, because union is the least-upper-bound function in the category of sets with their natural ordering relation. So if we implement, as has been done, `<` by `issubset` it is not worse to implement `max` by `union`.

I found some comments about it. Since `sort` uses `isless`, I would agree with @klacruâs suggestion to do the same with `max/maximum`.

1 Like

Iâd agree as well. Thanks for the discussion.

1 Like

Changing the definitions of `min` and `max` to use `isless` seems reasonable, although for non-floating-point types `<` and `isless` should be identical, so arguably the real bug here is that they differ for sets. The fact that `<` and `<=` are defined for sets is quite old and probably not a great idea â we have `â` and `â` operators that can be used for that. Defining `min` and `max` to compute intersection and union has a certain appeal, but I donât think itâs what people would really expect, and as noted would be inefficient. It seems more appropriate to introduce generic `meet` and `join` operations.

2 Likes

I should also note that making `min` and `max` perfectly commutative regardless of how `isless` is defined is not really practical â we have to assume that `isless` correctly defines a total order which is compatible with `isequal` in the sense that `!isless(a, b) && !isless(b, a)` if and only if `isequal(a, b)`. Given that is true, `min` and `max` will be commutative in the sense that `isequal(a, b)` implies that `isequal(min(a, b), min(b, a))` and `isequal(max(a, b), max(b, a))`. You may not have `min(a, b) === min(b, a)` however.

Issue opened: https://github.com/JuliaLang/julia/issues/23094.

2 Likes

I want to discus that a little bit. I restrict the consideration to non-numeric types.

That contradicts the documentation of `<` (see also `isless`).

<(x, y)

Less-than comparison operator. New numeric types should implement this function for two
arguments of the new type. Because of the behavior of floating-point NaN values, < implements
a partial order. Types with a canonical partial order should implement <, and types with a canonical total order should implement isless.

From the emphasised sentence, I conclude, that Types with a canonical partial order (and not a total order) must not implement `isless`. When trying to call `isless` for such types, a no-method-found exception should be thrown. When implementing `isless`, which is the indicator for a total order, the default implementation of `Base.<` in `operators.jl:194` redirects it to `isless`. So for total orders, your statement is correct, for non-total orders it is wrong.
`Set` behaves according to these guidelines.

That may be the case or not (I would have done it the opposite way, probably). But if we want to stick to the documentation, we have to implement it for partial orders.

If we modify `max` and `min` in the proposed way, I have no problem with that, as long as nobody expects to use `maximum` and `minimum` for collections of `Set`s.
Let us introduce generic `meet` and `join` operators in place of `min` and `max` for partial orders! For `AbstractSet` they should call `intersect` respectively `union`. Would we also provide methods of the same names for a variable amount of arguments and for collections of the ordered type? The names for the new functions are still under discussion.

The generic implementation of `max` and `min` would achieve the `===` though.

The name `join` is already used for other purposes, without a corresponding `meet`, whereas `supremum` and `infimum`, `sup` and `inf`, `lub` and `glb` seem quite free (or if used in packages, perhaps mean more or less the same as proposed here).

2 Likes

I agree that the current documentation does indicate that `<` and `<=` be used for âvery partialâ orders â like `Set`. However, we can change the documentation if that seems like a bad idea. There was a massive overhaul of hashing and equality here:

The intention after that was for `==` and `isequal` to be the same with the exception of floating-point values like -0.0 and 0.0 and NaN. If `==` is going to match `isequal` it would seem sensible for `<` and `isless` to match as well. Perhaps @jeff.bezanson can chime in about whether he still feels that `<` should be used for partial orders or not.

Iâm not sure if youâre saying that it should or that some proposed implementation would actually do so. I think this is considerably harder than one might imagine to do generically. Moreover, any definition of `min`/`max` which returns new mutable objects (e.g. unions or intersections) and not their actual argument values would not satisfy this for `===` so `isequal` is really the best one can hope for satisfying.

Sure, I didnât mean to use those names literally â âjoinâ in particular is quite overloaded. `infimum` and `supremum` are good names and there are plenty of Unicode operators available including `â§` and `â¨`. Also, thereâs no need to define any of these in Base Julia, this seems like good material for packages.

I prepared a working package `SupremumInfimum`, which implements `sup` and `inf`.
Feel free to try it out.

https://github.com/KlausC/SupremumInfimum.jl

@StefanKarpinski: Does that mean the generic implementation of `max` should be:
`max(x, y) = isless(y, x) ? (isimmutable(x) ? x : copy(x)) : isimmutable(y) ? y : copy(y)`
?

BTW, the current implementation of max is:
`max(x, y) = ifelse( y < x, x, y)` which implies `m === x` or `m === y`. I was thinking of that one.

It should be `max(x, y) = ifelse(isless(x, y), y, x)`. Any definitions of `isless` and `isequal` should have the following properties (in addition to the usual total pre-order properties for `isless` and equivalence relation properties for `isequal`):

1. For all `x` and `y`, at most one of `isless(x, y)` or `isless(y, x)` is true.
2. For all `x` and `y`, `isequal(x, y)` is true if and only if `!isless(x, y) && !isless(y, x)`.

As long as `isless` and `isequal` satisfy these properties, one can fairly easily see that `isequal(max(x, y), max(y, x))` for all `x` and `y`.