Re: [boost] [optional] operator<(optional<T>, T) -- is it wrong?

Subject: Re: [boost] [optional] operator<(optional<T>, T) -- is it wrong?
From: Vicente J. Botet Escriba (vicente.botet_at_[hidden])
Date: 2014-11-27 20:08:43

Le 27/11/14 23:44, Gavin Lambert a écrit :
> On 28/11/2014 05:12, Gottlob Frege wrote:
>> On Wed, Nov 26, 2014 at 6:49 PM, Gavin Lambert 
>> <gavinl_at_[hidden]> wrote:
>>> TBH, other than the "existing code" issue I'm not sure I like the 
>>> idea of
>>> std::less working but op< not -- and in particular if you don't 
>>> agree with
>>> the idea that "none is less than any other value" then I don't know why
>>> you'd agree with the idea that it should sort that way in a map, 
>>> which is
>>> what you appear to be suggesting.
>>
>> I don't like that std::less isn't the same as op< either, but it is
>> the best we currently have.  I hope to propose a fix for that -
>> something like std::order, which map and set would use instead of
>> std::less (and std::order would default to std::less for backwards
>> compatibility).
>
> I'm not sure I understand the meaning of having an order that isn't 
> implied by op<.  If op< is omitted because comparison is meaningless 
> or otherwise confusing, how could it be well-defined how to sort 
> them?  If there is not a single well-defined sort order, then the 
> library should not just pick one arbitrarily, and if there is, then 
> why would it not be appropriate as an op<?
There are a lot of kinds of orders 
(http://en.wikipedia.org/wiki/Total_order). Some of us would like that  
T < T mean the same kind of order thing independently of T. As we have 
already int < int that represents the natural order it follows that T < 
T should mean then the natural order. We can then have a lot of other 
orders that don't use this specific syntax. The order needed by the 
ordered containers is not the natural order but a strict week order ( 
http://en.wikipedia.org/wiki/Weak_ordering#Strict_weak_orderings ).
>
>> A good example of where std::order shouldn't be the same as op< would
>> be std::complex.  There isn't a sensible/natural mathematical way of
>> answering whether one complex number is larger than the other (while
>> at the same time getting the other properties we commonly expect from
>> a less-than).
>>
>> So std::complex shouldn't have op<.  But it would be nice to use them
>> in maps and other algorithms.  (Sure, we now have unordered_map, but
>> map/set still has uses.)
>>
>> And std::complex, looked at as a pair<Number, Number>, does have a
>> natural (lexicographical) ordering.
>>
>> So it would be nice if std::complex specialized std::order, but didn't
>> have op<.  If we don't get std::order, complex will probably
>> specialize std::less in the near future, because it is what works
>> today.
>
> I don't agree with any of that.  If you want to use it as a key for 
> something map/set-like, use unordered_map/set.  I can think of 
> multiple possible orderings of std::complex depending on application 
> need, and I don't think any one of them is inherently "better" than 
> any other.  So this should be left to the application to define the 
> sort order, in the rare case that this would actually be needed.
I think you are agreeing here, isn't it?
>
>>> But why do you want to have optional keys anyway?  When does it make 
>>> sense
>>> to have a single value attached to an empty key?  It's rare for a 
>>> dictionary
>>> type to permit null keys in any language.
>>>
>>
>> optional<T> is Regular if T if Regular.  The more that optional<T>
>> "just works" like int works, the better.   Particularly for generic
>> code.
>
> The first part sounds like a definition I am unfamiliar with.  I agree 
> with the second part, but I don't think it's relevant to this 
> discussion.  Nobody is talking about removing 
> op<(optional<T>,optional<T>), which is what generic code would use. 
optional<int> is the sum of none and T. If T has a natural order, the 
natural order of the sum can be defined. So optional<T> should define 
operator < only if T defines it.
> Any generic code that *could* use both T and optional<T> must by 
> definition be aware of the fact that it's using optional, so will 
> either know that op<(optional<T>,T) is not sensible and avoid using it 
> or will explicitly convert as needed so that it invokes 
> op<(optional<T>,optional<T>) instead. 
The problem is not the operator w, but the implicit conversions.
> Alternatively it must be aware that it is using different types, so 
> op< may not be sane between them.  Either way I don't think this would 
> be a problem in real code.
>
> However possibly there might need to be a type trait specialization 
> that explicitly denies op<(optional<T>,T) and the reverse, to avoid 
> confusing code that attempts to detect when op< does work between 
> distinct types.
I don't think this follow "make simple things simple".
>
>> For less-than we have these competing points, (that each of us may
>> weigh differently)
>>
>> 0 - std::less should be same as op<
>> (I think we all agree here, actually, which is why we should have 
>> std::order)
Only if op< id defined.
>>
>> 1 - op<(optional<T>, optional<T>) is "sensible" but somewhat arbitrary
I don't agree here. We don't need anything arbitrary. 
op<optional<T>,optional<T>) must be defined only if op<(T,T> is defined.
>> 2 - op<(optional<T>, T) is questionable, often (usually?) wrong
Agreed.
>> 3 - in general, func(optional<T>, optional<T>) should work if passed
>> T's (ie implicit conversion is important)
I have my doubts here. Implicit conversions provide often (usually?) 
unexpected behavior.
>> 4 - op<(optional<T>, optional<T>) *is* of the form func(optional<T>,
>> optional<T>) - ie why should it be different?
Nothing to say here ;-)
>
> All true.
>
>> 2 and 3, to me, are the strongest, but directly opposed.
>> How do you solve that?
>> Either say
>>
>> A1. "well operators are special, not typical functions" so we can
>> poison them while keeping general functions implicit
>> A2. 1 is on shaky ground, so let's remove both 1 and 2, but keep
>> std::less/std::order, which was the main reason for having op<.
>
> Of these, I prefer A1.  I think it really is a special case.  But I 
> can understand why the present behaviour is as it is.
>
> I suspect those who dislike "none" having a defined order would go for 
> A2 though.  I would be ok with that as well, but I don't have a 
> problem with this definition.
>
> But you're leaving out A3: remove 1+2 AND std::less/std::order. This 
> means that optional types can't be used in map keys, only in 
> unordered_map.  I actually think that this is the best option, except 
> that it has a greater potential to break existing code. Perhaps a 
> predicate could be defined specific to optional giving the current 
> ordering, so that users who do want that ordering or to continue using 
> a map could just specify that predicate as a minimal fix.  But I don't 
> think that the predicate should be spelled "std::less".
>
Currently we have std::less, not std::order and the STL ordered 
containers are using as default comparator std::less. So let define 
std::less<optional<T>> using std::less<T>.

Vicente

P.S. For some mathematical fundation on sum types see 
http://en.wikipedia.org/wiki/Tagged_union
For some examples of optional type on other languages, see 
http://en.wikipedia.org/wiki/Option_type