Terrible bug: Double.NaN compares true!

[G J]

This is scala version 2.9.2.

scala> Double.NaN > 1.0
res0: Boolean = false                                                    // as expected

scala> def f(implicit n: Numeric[Double]) = n.gt _
f: (implicit n: Numeric[Double])(Double, Double) => Boolean

scala> val gt = f
gt: (Double, Double) => Boolean = <function2>

scala> gt(Double.NaN, 1.0)
res1: Boolean = true

I haven't switched to 2.10 yet, and have not tried it there either.

Best Regards.

[Rex Kerr]

Ouch, that is a bad one, or it would be if anyone used Numeric for anything important.  (I don't; it's historically been too slow.)  File a bug report?

  --Rex

[Ryan Hendrickson]

Two arguments (or maybe one argument wearing two different colored shirts) against this being a bug:

1. Numeric extends Ordering, not (merely) PartialOrdering; so under the total ordering defined by Numeric, NaN should be either greater than, less than, or equal to 1.0. Pick one.

2. Blame Java:

scala> java.lang.Double.compare(Double.NaN, 1.0)
res0: Int = 1

(please forgive me my corporate legal disclaimer)

----------------------------------------

This message is intended exclusively for the individual(s) or entity to
which it is addressed. It may contain information that is proprietary,
privileged or confidential or otherwise legally exempt from disclosure.
If you are not the named addressee, you are not authorized to read,
print, retain, copy or disseminate this message or any part of it.
If you have received this message in error, please notify the sender
immediately by e-mail and delete all copies of the message.

[Paul Phillips]

On Mon, Jan 7, 2013 at 11:34 AM, Ryan Hendrickson <Ryan.Hen...@bwater.com> wrote:

Two arguments (or maybe one argument wearing two different colored shirts) against this being a bug:

An argument for it being a bug is that it returns false in 2.10, and I cling to the hope that we progress more than we regress.

[Erik Osheim]

On Mon, Jan 07, 2013 at 02:34:04PM -0500, Ryan Hendrickson wrote:
> Two arguments (or maybe one argument wearing two different colored shirts) against this being a bug:
>
> 1. Numeric extends Ordering, not (merely) PartialOrdering; so under the total ordering defined by Numeric, NaN should be either greater than, less than, or equal to 1.0. Pick one.
>
> 2. Blame Java:
>
> scala> java.lang.Double.compare(Double.NaN, 1.0)
> res0: Int = 1

Agreed. If you consider Double to have a total order, the only other
behavior you could have for compare would be to throw an error. Maybe
this is better? I'm not sure.

Unfortunately the problem isn't limited to Numeric. Sorting a
colleciton of Doubles (using Ordering) will potentially hit this issue
as well. While it's true that Numeric is slow, many people do end up
using it inadvertantly.

Spire currently dispatches to java.lang.Double.compare for this, but I
could easily be persuaded to adopt some other behavior. In Spire
there's essentially no penalty for using Numeric/Order/etc versus
concrete code, so I do think it's worth figuring out a good solution.

-- Erik

P.S. I've imagined writing a tongue-in-cheek PartialOrder with a
compare function that returns a Float (supporting negative, zero,
positive, or NaN results).

[G J]

If I recall, IEEE spec says NaN compares false with everything including itself. The only case where it returns true is in the 'unordered' comparison.

It's been years since I looked at the IEEE spec, but if the above continues to hold,  then Java got it wrong.

Best Regards.

[Rex Kerr]

On Mon, Jan 7, 2013 at 2:34 PM, Ryan Hendrickson <Ryan.Hen...@bwater.com> wrote:

Two arguments (or maybe one argument wearing two different colored shirts) against this being a bug:

1. Numeric extends Ordering, not (merely) PartialOrdering; so under the total ordering defined by Numeric, NaN should be either greater than, less than, or equal to 1.0. Pick one.

This is exactly the problem.  Double is Numeric, but not Ordered.  It's orderable but intrinsically all NaN comparisons will return false (save not-equal, which returns true even if it's NaN != NaN), and all arithmetic with NaN will return NaN.  You can break the tie by deciding where to put your NaNs.

 

 

2. Blame Java:

scala> java.lang.Double.compare(Double.NaN, 1.0)
res0: Int = 1

Java has broken the tie by deciding to sort NaNs to the end.  This is perfectly reasonable.  compare is  for sorting.  This is more questionable:

scala> java.lang.Double.compare(Double.NaN, Double.NaN)
res60: Int = 0

Anyway, the problem is when you _think_ you're doing a regular greater-than and you're _actually_ doing a greater-than to produce a total order on Double.  It is confusing, admittedly, that both senses exist simultaneously (one driven by the demands of having a None value, the other by the demands of sorting in place).

  --Rex

 

[Paul Phillips]

On Mon, Jan 7, 2013 at 11:58 AM, G J <oda...@gmail.com> wrote:

If I recall, IEEE spec says NaN compares false with everything including itself. The only case where it returns true is in the 'unordered' comparison.

It's been years since I looked at the IEEE spec, but if the above continues to hold,  then Java got it wrong.

Volumes have been written on this matter. Java made the boxed NaN compare equal to itself so you wouldn't forever lose any NaNs you put into a map. They left primitive NaN in its happy NaN != NaN place.

Scala came along and unified boxed and unboxed. At that point to keep everything working, we had to maintain these two invariants:

  NaN == NaN

  NaN != NaN

I expect a breakthrough any day.

[Ryan Hendrickson]

Yes, that's what the spec says, which is why the operators work the way they do.

There is occasionally a need for a total ordering on doubles, however, for such applications as sorting lists of doubles which might include NaN. That is the purpose of java.lang.Double.compare, and it's a good thing that that exists, although perhaps it could be named more clearly to avoid misleading people.

I would like for these two things to be able to happily coexist somehow; they don't directly conflict with each other, as long as you understand that the former is a partial order and the latter is a total order which includes the partial order as a subrelation.

It appears, however, that one of the committers disagrees with me:

https://issues.scala-lang.org/browse/SI-5104
https://github.com/scala/scala/commit/460bbc1276fb4ba83b9bcbdc7f7ba475b352b7c6

The situation in 2.10 has traded one consistency for another: now Ordering.Double.compare is implemented in terms of the total ordering, and the other methods of Ordering.Double only respect the partial ordering. This makes gt and friends agree with > and friends, but it breaks the assumption that _ gt _ is true iff compare(_, _) is positive.

I'm not sure how I feel about this tradeoff (I would like to believe that this change was made because smarter people than I thought about this problem and chose this solution for good reasons), but at least everyone should be aware that these are the facts on the ground.

[Chris Sachs]

On Mon, Jan 7, 2013 at 11:40 AM, Erik Osheim <er...@plastic-idolatry.com> wrote:

P.S. I've imagined writing a tongue-in-cheek PartialOrder with a
compare function that returns a Float (supporting negative, zero,
positive, or NaN results).

This makes the most sense. I favor this implementation for float comparison:

def compare(x: Double, y: Double): Double = x - y

You can choose to ignore -0.0 if you please. But NaNs never match. Those IEEE guys put a lot of thought into floating point arithmetic, why throw it out for ordering's sake? It sure beats the Option[Int] baloney in Scala's PartialOrder.

-- Chris Sachs

[Erik Osheim]

On Mon, Jan 07, 2013 at 03:13:04PM -0500, Rex Kerr wrote:
> Anyway, the problem is when you _think_ you're doing a regular greater-than
> and you're _actually_ doing a greater-than to produce a total order on
> Double. It is confusing, admittedly, that both senses exist simultaneously
> (one driven by the demands of having a None value, the other by the demands
> of sorting in place).

I think we're agreed about what should be happening, right?

1. compare is mildly broken, in that compare(NaN, NaN) == 0
2. everything else works as expected
(NaN is not greater than, less than, or equal to anything, even NaN)

This is the behavior 2.10 has (unlike 2.9) which seems as correct as it
can be given the existence of an Ordering[Double] with a compare method
that returns Int.

(Spire's Order[Double] also has this behavior currently.)

-- Erik

[G J]

What is the best way to access the native comparison operators when a type parameter is bound to Double?

Specifically (and contrived):

    trait  X[T] {
          def   > (b: X[T]) (implicit n: Numeric[T]) =
    }

Numeric[T] is not the answer as it is bound to the totally ordered comparison for doubles.

Thanks.

Best Regards.

[er...@plastic-idolatry.com]

On Mon, Jan 07, 2013 at 08:23:08PM -0800, G J wrote:
> What is the best way to access the native comparison operators when a type
> parameter is bound to Double?
>
> Specifically (and contrived):
>

> *trait* X[T] {
> *def* > (b: X[T]) (*implicit* n: Numeric[T]) =

> }
>
> Numeric[T] is not the answer as it is bound to the totally ordered
> comparison for doubles.

On 2.10 less-than, greater-than, etc will express Double's partial
ordering just fine. It's only compare that you need to stay away from.
This is on 2.10.0:

scala> import scala.math.Ordering.Implicits._
import scala.math.Ordering.Implicits._

scala> def test[T: Ordering](a: T, b: T) = a < b
test: [T](a: T, b: T)(implicit evidence$1: Ordering[T])Boolean

scala> test(Double.NaN, 3.0)
res0: Boolean = false

scala> test(3.0, Double.NaN)
res1: Boolean = false

Looks fine, no?

-- Erik

[G J]

Yes. That works perfectly.

btw: 2.9.2 behaves differently. 

Mine is not to reason why, but to switch to 2.10.

Thanks.

Best Regards.

[Ryan Hendrickson]

> This is the behavior 2.10 has (unlike 2.9) which seems as correct as it
> can be given the existence of an Ordering[Double] with a compare method
> that returns Int.

Except that this behavior leads directly to this bug:

scala> val a = Array(1.0, 2.0, 5.0, Double.NaN, 4.0, 2.0)
a: Array[Double] = Array(1.0, 2.0, 5.0, NaN, 4.0, 2.0)

scala> util.Sorting.stableSort(a)

scala> a
res0: Array[Double] = Array(1.0, 2.0, 5.0, NaN, 2.0, 4.0)

The cause of the bug is that stableSort assumes that Ordering.lt is a total order, which was presumably true at the time when those sorting functions were written, but now in the case of Double is false.

One possible approach is to say, okay, if you really, really care about Ordering being a total order, you have to use compare all the time and never use any other method on that typeclass, tempting though they may appear. If that's the answer, at the very least, I would want the documentation on Ordering should say something to the effect; right now there is no hint that this sort of treachery is possible.

> (Spire's Order[Double] also has this behavior currently.)

That's a pity. I was hoping you'd take a more purist approach with Spire--although I haven't worked with it yet; does Order in Spire have a stated disposition on whether it is total or partial? Do sorting functions in Spire suffer from the same bug?

[Paul Phillips]

On Tue, Jan 8, 2013 at 4:48 AM, G J <oda...@gmail.com> wrote:

btw: 2.9.2 behaves differently. 

Mine is not to reason why, but to switch to 2.10.

If you guys like the behavior in 2.10, I strongly urge you to verify that some test case covers the relevant behaviors, and to submit a new test if that's not the case.

[Erik Osheim]

(response below)

On Tue, Jan 08, 2013 at 11:16:33AM -0500, Ryan Hendrickson wrote:
> The cause of the bug is that stableSort assumes that Ordering.lt is a
> total order, which was presumably true at the time when those sorting
> functions were written, but now in the case of Double is false.

...

> That's a pity. I was hoping you'd take a more purist approach with
> Spire--although I haven't worked with it yet; does Order in Spire have
> a stated disposition on whether it is total or partial? Do sorting
> functions in Spire suffer from the same bug?

Interesting. I can understand your frustration but I don't see this
approach as less purist. Any numeric class based on AnyRef has the same
problem that Double does: an undefined element (NaN or null) that makes
any ordering non-total (and breaks the rules... Nan + 0 -> NaN). In the
case of null the sort will explode rather than return a
partially-sorted result, which isn't clearly better or worse, just
different.

Spire does not currently implement a PartialOrder because we haven't
seen use cases or algorithms where partial ordering produces a useful
result. Implementing the class is easy though so if someone has a use
for it then it won't be a problem.

Spire currently display the same behavior as Scala in this case. I'm
not sure it's really a bug, but if there isn't a huge cost to use
compare instead I will definitely change it.

That said, I don't think producing a total ordering on Double that
makes NaN greater than (or less than) all other values is principled.
Like null, NaN breaks the rules and I don't think we should wring our
hands too much about it. Losing total orderings for Float, Double, and
AnyRef types sounds terrible, and producing an order where NaN > Inf
(and NaN == NaN) doesn't seem much better.

-- Erik

[er...@plastic-idolatry.com]

On Tue, Jan 08, 2013 at 08:40:14AM -0800, Paul Phillips wrote:
> If you guys like the behavior in 2.10, I strongly urge you to verify that
> some test case covers the relevant behaviors, and to submit a new test if
> that's not the case.

Will do.

[Erik Osheim]

On Tue, Jan 08, 2013 at 11:56:41AM -0500, Erik Osheim wrote:
> Interesting. I can understand your frustration but I don't see this
> approach as less purist. Any numeric class based on AnyRef has the same
> problem that Double does: an undefined element (NaN or null) that makes
> any ordering non-total (and breaks the rules... Nan + 0 -> NaN). In the
> case of null the sort will explode rather than return a
> partially-sorted result, which isn't clearly better or worse, just
> different.

Sorry, I should have said NaN + 1 -> NaN. Obviously if you try to do
algebra with NaN you'll hit contradcitions very quickly.

-- Erik

[Ryan Hendrickson]

> > That's a pity. I was hoping you'd take a more purist approach with
> > Spire--although I haven't worked with it yet; does Order in Spire have
> > a stated disposition on whether it is total or partial? Do sorting
> > functions in Spire suffer from the same bug?
>
> Interesting. I can understand your frustration but I don't see this
> approach as less purist. Any numeric class based on AnyRef has the same
> problem that Double does: an undefined element (NaN or null) that makes
> any ordering non-total (and breaks the rules... Nan + 0 -> NaN). In the
> case of null the sort will explode rather than return a
> partially-sorted result, which isn't clearly better or worse, just
> different.

Well, if NaN gets a free pass because it breaks the rules, why not choose to construct the instance of Order such that it disagrees with the primitive operators on NaN but agrees with its own invariants? There's nothing internally inconsistent about defining a total ordering on Double; yes, it doesn't make Double into an ordered field, but it can still be a perfectly well-defined total ordering. There is, however, something internally inconsistent about defining a total ordering where NaN is neither greater than, less than, or equal to another Double.

(I would indeed make the same argument for null, except that I find throwing an exception to be a perfectly acceptable response to receiving unexpected input, whereas I feel much worse about silently returning incorrect results.)

I guess that's what I meant by purist; I think this comes down to a tradeoff between returning the same results as the primitive operators and adhering to the contract of a total order, one of which is a specialized set of compromises constructed for this particular data type, and the other of which is a rigorous mathematical concept. I can see how Team Scala might decide that they would want to compromise the latter for the former in this case, given the general audience of Scala users, but my expectation was that a library with a strong pure math focus would come down hard on the side of upholding the invariants of its typeclasses.

Obviously you can take my opinion about your library which I have not used extensively for exactly how little it's worth. Just trying to explain where I was coming from with that comment, as most of what I've seen of the design of Spire is very appealing to me and I thought you might be interested.

[Erik Osheim]

[Erik Osheim]

Please disregard that, my mail client got away from me.

Ryan, I'll think on your points and respond. One of the nice the type
class approach gives us is that it's easy for users to override the
"default" ordering and use their own. :)

-- Erik

[Rex Kerr]

On Tue, Jan 8, 2013 at 4:11 PM, Ryan Hendrickson <Ryan.Hen...@bwater.com> wrote:

Well, if NaN gets a free pass because it breaks the rules, why not choose to construct the instance of Order such that it disagrees with the primitive operators on NaN but agrees with its own invariants?

val a = Array(1.0, Double.NaN, 3.0)

var mx = a(0)

i = 1

while (i < a.length) { if (a(i) > mx) { mx = a(i) }; i += 1 }

var my = Double.NaN

i = 0

while (i < a.length) { if (my < a(i)) { my = a(i) }; i += 1 }

var mn = a(0)

i = 1

while (i < a.length) { if (a(i) < mn) { mn = a(i) }; i += 1 }

var mm = Double.NaN

i = 0

while (i < a.length) { if (a(i) > mm) { mm = a(i) }; i += 1 }

This is really powerful, and a good argument for the way things currently are.  A little cryptic, granted, but very efficient and flexible.

If your sort algorithm expects this kind of behavior, it can do the right thing for free instead of creating a spurious integer.

  --Rex

[Szabolcs Berecz]

It was probably me who introduced the change between 2.9 and 2.10 while fixing https://issues.scala-lang.org/browse/SI-5104

This is the commit: https://github.com/scala/scala/commit/460bbc1276fb4ba83b9bcbdc7f7ba475b352b7c6
Tests are here: https://github.com/scala/scala/blob/master/test/files/scalacheck/nan-ordering.scala

I think it does the right thing where it can. I have not read this thread through, though. Will do it later.

[Oliver Ruebenacker]

Hello,

Conventional wisdom is that comparing +Inf, -Inf and NaN to
themselves should always yield false. The reasoning is that they
represent unknown values, and if two expressions both yield, say,
+Inf, they are probably not the same mathematically. However, this is
true for any two expressions, since Doubles are approximate by nature.
This means even if two different expressions both produce, say, 1.23,
it does not necessarily mean that they were supposed to be the same
mathematically, since the results are always approximate.

For example, compare 1.0 with (1.0 + 1e-1000), and you will be
falsely told they are equal.

The only clean way to Double equality is therefore this:

Two Double values are equal if and only if they have been produced
by the same expression. In other words, default Object equality. This
can be held true for regular Double values as well as for +Inf, -Inf
and NaN.

What if the same expression is evaluated twice? I would suggest it
should be undefined whether the two results are equal or not. Doubles
are approximate, so no one should expect more.

That leaves the question, what about lesser and greater than, for
distinct but indistinguishable Double values? Say, we have (2.0 + 2.0)
and (2.0*2.0), and since these are different expressions, so the
results should be considered different. What if they happen to result
in the same underlying double value? In this case, one of them should
be considered larger, and it should be undefined, which one. But we
should be consistent, so if one has been found larger, it should still
be larger if compared a second time.

Take care
Oliver

--
IT Project Lead at PanGenX (http://www.pangenx.com)
The purpose is always improvement

[Rex Kerr]

On Wed, Jan 9, 2013 at 9:47 AM, Oliver Ruebenacker <cur...@gmail.com> wrote:

     Hello,

  Conventional wisdom is that comparing +Inf, -Inf and NaN to
themselves should always yield false.

I don't think that's conventional wisdom in the programming world.  Scala says:

val Inf = Double.PositiveInfinity
val nInf = Double.NegativeInfinity
val NaN = Double.NaN

Inf == Inf   // true

nInf == nInf // true

nInf ==Inf // false (I should think so!)

Inf == NaN // false

nInf == NaN // false

NaN == NaN //false

Makes sense to me, inasmuch as NaN is a "no value found" and you need to propagate that state as best you can via standard operations.

 

  For example, compare 1.0 with (1.0 + 1e-1000), and you will be
falsely told they are equal.

No, you're comparing 1.0 to 1.0 and being correctly told that they are the same.

It is the (1.0 + 1e-1000)  calculation that goes awry.

Actually, 1e-1000 goes awry because it cannot be represented in a Double, so the compiler should really warn you.  ("This constant should be written 0.0".)  1.0+1e-20 is a better example of something that loses precision on addition, but again, it's the addition that goes awry not the equality.

  --Rex

 

[Scott Carey]

Yes, much of this discussion seems to be avoiding the fact that both are true (in different contexts).

For arithmetic NaN != NaN
For order, NaN == NaN

(and similarly for null or any other value representing various classes of the unknown)

This is how SQL works.  You can sort or group numeric values in a database and expect NaN (or null) to be grouped together.  However, the relation 'NaN' = X and null = X will return false for any value of X.

Arithmetic equality != Ordering equality.  Conflating the two leads to great pain and suffering.

[Robert Kirkpatrick]

Correction: every comparison to NULL in SQL yields NULL !
This is the only way out of these sufferings: ternary logic.

Arithmetic equality != Ordering equality.  Conflating the two leads to great pain and suffering.

Kr,
Robert.

[Oliver Ruebenacker]

Hello,

On Wed, Jan 9, 2013 at 10:52 AM, Rex Kerr <ich...@gmail.com> wrote:
>
>
>
> On Wed, Jan 9, 2013 at 9:47 AM, Oliver Ruebenacker <cur...@gmail.com> wrote:
>>
>> Hello,
>>
>> Conventional wisdom is that comparing +Inf, -Inf and NaN to
>> themselves should always yield false.
>
>
> I don't think that's conventional wisdom in the programming world. Scala
> says:
>
> val Inf = Double.PositiveInfinity
> val nInf = Double.NegativeInfinity
> val NaN = Double.NaN
>
> Inf == Inf // true
> nInf == nInf // true
> nInf ==Inf // false (I should think so!)
> Inf == NaN // false
> nInf == NaN // false
> NaN == NaN //false

I didn't know that Double.Infinity==Double.Infinity in Scala, and
I'm not sure it makes sense, since inf for double is almost synonymous
for "a number too large to represent as a regular double". Consider:

scala> val x = 1e200*1e200
x: Double = Infinity

> Makes sense to me, inasmuch as NaN is a "no value found" and you need to
> propagate that state as best you can via standard operations.

I don't understand that "no value found" metaphor, since we aren't querying.

>> For example, compare 1.0 with (1.0 + 1e-1000), and you will be
>> falsely told they are equal.
>
> No, you're comparing 1.0 to 1.0 and being correctly told that they are the
> same.

You are right that the two values are the same. The point is that
comparison of double values fails to reflect mathematical reality,
since in math, (1+1e-20) is different from 1.

> It is the (1.0 + 1e-1000) calculation that goes awry.
>
> Actually, 1e-1000 goes awry because it cannot be represented in a Double, so
> the compiler should really warn you. ("This constant should be written
> 0.0".) 1.0+1e-20 is a better example of something that loses precision on
> addition, but again, it's the addition that goes awry not the equality.

It depends what question we ask. If we merely want to know whether
we have the same two double values, equality works fine. By that
standard, we could consider NaN==NaN fine, too. If the question is
whether it will always reflect mathematical reality, then equality
fails.

Take care
Oliver

[Rex Kerr]

On Wed, Jan 9, 2013 at 3:06 PM, Oliver Ruebenacker <cur...@gmail.com> wrote:

    

  I didn't know that Double.Infinity==Double.Infinity in Scala

That's the IEEE standard.

 

, and
I'm not sure it makes sense, since inf for double is almost synonymous
for "a number too large to represent as a regular double". Consider:

scala> val x = 1e200*1e200
x: Double = Infinity

> Makes sense to me, inasmuch as NaN is a "no value found" and you need to
> propagate that state as best you can via standard operations.

  I don't understand that "no value found" metaphor, since we aren't querying.

You don't *think* you are.  But you are, because some operations do not have a valid result.

 

>>   For example, compare 1.0 with (1.0 + 1e-1000), and you will be
>> falsely told they are equal.
>
> No, you're comparing 1.0 to 1.0 and being correctly told that they are the
> same.

  You are right that the two values are the same. The point is that
comparison of double values fails to reflect mathematical reality,
since in math, (1+1e-20) is different from 1.

Argh.  It has nothing to do with comparison.  Nothing at all, except inasmuch as eventually you probably want to compare a number with another number.

Normally we work with the reals as a field: <R,+,-,0,*,^(-1),1> with all the usual rules.  Unfortunately, the zero is not unique for all elements, and if you view doubles as closed under mathematical operations then the existence of inverses and distributivity over multiplication are violated.  (Or you can view it as not closed, and then there are more violations of closure and fewer violations of existence of inverses.)

So doubles are a messed up field.  Pretending that it's the comparison that's awry is supremely unhelpful because you cannot fix the problem by working on the comparison operators.

Addition of double values is what fails to reflect mathematical reality in your example, as 1e-20 is not 0, so (1+1e-20) is not supposed to be 1, but with doubles it is.  Whether you detect this error by comparison, inversion, printing, or something else is immaterial.

  --Rex

[Ryan Hendrickson]

> Well, if NaN gets a free pass because it breaks the rules, why
> not choose to construct the instance of Order such that it disagrees
> with the primitive operators on NaN but agrees with its own invariants?
>
>
> val a = Array(1.0, Double.NaN, 3.0)
>
>
> var mx = a(0)
>
> i = 1
>
> while (i < a.length) { if (a(i) > mx) { mx = a(i) }; i += 1 }
>
>
> var my = Double.NaN
>
> i = 0
>
> while (i < a.length) { if (my < a(i)) { my = a(i) }; i += 1 }
>
>
> var mn = a(0)
>
> i = 1
>
> while (i < a.length) { if (a(i) < mn) { mn = a(i) }; i += 1 }
>
>
> var mm = Double.NaN
>
> i = 0
>
> while (i < a.length) { if (a(i) > mm) { mm = a(i) }; i += 1 }
>
>
> This is really powerful, and a good argument for the way things
> currently are. A little cryptic, granted, but very efficient and
> flexible.

It seems like you're making a simple point with these examples, and I feel like an idiot for not getting it. Would you mind explaining what it is that you're demonstrating here?

What I see are four algorithms for finding the min and max of arrays of doubles, except that the my and mm ones get stuck on their initial Double.NaN value (and mm looks identical to my, which I assume is just a typo and not relevant to your point). I'm not sure why you would ever write the my or mm code, but the mx and mn ones do indeed look useful, and I would not want them to go away. I would not advocate changing anything about the way that the < and > methods on Double work.

I would merely argue that the desired behavior in mx and mm is not consistent with any sort of total ordering on Double, and thus if one is writing generic min/max functions that take an implicit Ordering[Double], one should not expect a way to get that behavior, nor should one violate the contract of Ordering in the name of getting that behavior out of such generic functions. This behavior is specific to IEEE floating-point data; let it be typed accordingly.

(Or, if we must violate the contract in the name of not surprising people who are not as hung-up on mathematical rigor as I am, document this fact prominently so people writing sorting algorithms are not tripped up by using gt when they should use compare > 0.)

[Daniel Sobral]

It reminds me that multiplying an object by an array in Javascript is
"Not a Number". :-) Or some other similar operation (see the "wah!"
video for details).

--
Daniel C. Sobral

I travel to the future all the time.

[Rex Kerr]

On Wed, Jan 9, 2013 at 4:24 PM, Ryan Hendrickson <Ryan.Hen...@bwater.com> wrote:

>       Well, if NaN gets a free pass because it breaks the rules, why
> not choose to construct the instance of Order such that it disagrees
> with the primitive operators on NaN but agrees with its own invariants?
>
>
> val a = Array(1.0, Double.NaN, 3.0)
>
>
> var mx = a(0)
>
> i = 1
>
> while (i < a.length) { if (a(i) > mx) { mx = a(i) }; i += 1 }
>
>
> var my = Double.NaN
>
> i = 0
>
> while (i < a.length) { if (my < a(i)) { my = a(i) }; i += 1 }
>
>
> var mn = a(0)
>
> i = 1
>
> while (i < a.length) { if (a(i) < mn) { mn = a(i) }; i += 1 }
>
>
> var mm = Double.NaN
>
> i = 0
>
> while (i < a.length) { if (a(i) > mm) { mm = a(i) }; i += 1 }
>
>
> This is really powerful, and a good argument for the way things
> currently are.  A little cryptic, granted, but very efficient and
> flexible.

It seems like you're making a simple point with these examples, and I feel like an idiot for not getting it. Would you mind explaining what it is that you're demonstrating here?

What I see are four algorithms for finding the min and max of arrays of doubles, except that the my and mm ones get stuck on their initial Double.NaN value (and mm looks identical to my, which I assume is just a typo and not relevant to your point).

Sorry, I retract my point.  There are times where NaN will automatically do the right thing, but this isn't one of them.  Thanks for catching this.

At some point when I have more time I'll explain what I actually meant, which was more complicated than this and I ended up oversimplifying too much when trying to quickly give an example.

But since it is more complicated, losing the capability is less important than I claimed.

  --Rex

[Erik Osheim]

On Tue, Jan 08, 2013 at 04:11:56PM -0500, Ryan Hendrickson wrote:

> Well, if NaN gets a free pass because it breaks the rules, why not
> choose to construct the instance of Order such that it disagrees with
> the primitive operators on NaN but agrees with its own invariants?
> There's nothing internally inconsistent about defining a total ordering
> on Double; yes, it doesn't make Double into an ordered field, but it
> can still be a perfectly well-defined total ordering. There is,
> however, something internally inconsistent about defining a total
> ordering where NaN is neither greater than, less than, or equal to
> another Double.

Spire has a bunch of goals, one of which is to produce generic code
that runs as if you'd written a direct implementation. Dispatching to
the primitive operators has the appeal of being fast and not changing
these semantics.

I think the best way forward for Spire is to do the following:

1. Provide alternate typeclass with a total ordering including NaN.

2. Document the current behavior in an easy-to-find place, including:
a. NaN comparison semantics
b. Using compare() to get total order
c. How to import alternate implementations
d. Other floating point considerations and warnings

3. Consider altering things like sort to use compare().

I will also benchmark the cost of using the alternate typeclass
instance, to see what effect (if any) it has.

> Obviously you can take my opinion about your library which I have not
> used extensively for exactly how little it's worth. Just trying to
> explain where I was coming from with that comment, as most of what I've
> seen of the design of Spire is very appealing to me and I thought you
> might be interested.

Not at all. Thanks for your feedback.

These things are always trade-offs and it's really valuable to get
people's perspectives. Of course if there is a lot of demand for a
"more pure" Order[Double] it's a real argument in favor of changing the
default behavior.

-- Erik

[Rex Kerr]

The point I was trying to make--and failed to, which is also a lesson regarding relying upon the not-entirely-trivial NaN behavior--is that you can use the NaN properties to implicitly make things work out properly without having to do extra checks.

For example, you can use it with input validation.  Suppose you create a function that is defined only for positive integers.  You could

  def f(x: Double) = {

    if (x <= 0 || x.isNaN) throw new IllegalArgumentException

    else log(x)*sqrt(x)
  }

Or you could simply

  def f(x: Double) = {

    if (x > 0) log(x)*sqrt(x)

    else throw new IllegalArgumentException
  }

Where'd the NaN check go?  Why, into the comparison logic.

You can also avoid NaNs when looking for maximum values:

  var found = Double.NegativeInfinity

  var i = 0

  while (i < a.length) {

    if (a(i) > found) found = a(i)

    i += 1
  }

Again, no explicit NaN check needed.

  --Rex

[Ryan Hendrickson]

> The point I was trying to make--and failed to, which is also a lesson
> regarding relying upon the not-entirely-trivial NaN behavior--is that
> you can use the NaN properties to implicitly make things work out
> properly without having to do extra checks.

Yes, agreed. The IEEE definition of floating-point operations allows for some clever optimizations which, when used carefully, can result in code that does the right thing and is both easy to read and efficient. No arguments there. Long live Double.> and friends in their current forms.

My only contention is whether it is acceptable for a canonical instance of a typeclass to violate the documented invariants of the typeclass, and whether consumers of that typeclass should have to bear the cognitive burden of expecting those invariants to be violated sometimes.

[Ryan Hendrickson]

> Spire has a bunch of goals, one of which is to produce generic code
> that runs as if you'd written a direct implementation. Dispatching to
> the primitive operators has the appeal of being fast and not changing
> these semantics.

Ah, that makes sense then. If a big value of Spire is that you can use all these fancy abstractions and not lose any efficiency no-really-stop-worrying-about-it, and you also take (and document) the perspective of 'use NaN at your own risk, like null', I totally see why you'd want to make that call.

> I think the best way forward for Spire is to do the following:
>
> 1. Provide alternate typeclass with a total ordering including NaN.
>
> 2. Document the current behavior in an easy-to-find place, including:
> a. NaN comparison semantics
> b. Using compare() to get total order
> c. How to import alternate implementations
> d. Other floating point considerations and warnings
>
> 3. Consider altering things like sort to use compare().

Sounds reasonable. Thanks for taking the time!

[Chris Sachs]

On Wed, Jan 9, 2013 at 5:01 PM, Rex Kerr <ich...@gmail.com> wrote:

The point I was trying to make--and failed to, which is also a lesson regarding relying upon the not-entirely-trivial NaN behavior--is that you can use the NaN properties to implicitly make things work out properly without having to do extra checks.

This is exactly why I favor making Ordering.compare return a Float.

trait Ordering[T] {

}

[Chris Sachs]

Note to self: don't tab-return in GMail. Sorry about that.

On Thu, Jan 10, 2013 at 10:49 AM, Chris Sachs <ch...@reify.it> wrote:

On Wed, Jan 9, 2013 at 5:01 PM, Rex Kerr <ich...@gmail.com> wrote:

The point I was trying to make--and failed to, which is also a lesson regarding relying upon the not-entirely-trivial NaN behavior--is that you can use the NaN properties to implicitly make things work out properly without having to do extra checks.

This is why I favor making Ordering.compare return a Float.

trait Ordering[T] {

  def compare(x: T, y: T): Float

}

object Ordering {

  def compare[T : Ordering](x: T, y: T): Float = implicitly[Ordering[T]].compare(x, y)

  implicit object Double extends Ordering[Double] {

    override def compare(x: Double, y: Double): Float = (x - y).toFloat

  }

}

import Double.{NaN, PositiveInfinity, NegativeInfinity}

import Ordering.compare

compare(-0.0, 0.0) // -0.0

compare(0.0, -0.0) // 0.0

compare(NaN, NaN) // NaN

compare(PositiveInfinity, PositiveInfinity) // NaN

compare(NegativeInfinity, NegativeInfinity) // NaN

compare(PositiveInfinity, NegativeInfinity) // Infinity

compare(NegativeInfinity, PositiveInfinity) // -Infinity

These results let sorting algorithms handle off-nominal cases however they choose. The sorting algorithm, not the ordering, should decide if incomparable values sort first or last. It seems like a win-win to me. Existing logic that compares values against 0: Int should continue to work; though they'll probably randomly intersperse NaNs. I think we should model total orders like floats model reals, which is to say they don't exactly; that's reality.

-- Chris Sachs