Mystery of an Eq instance

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
34 messages Options
12
Reply | Threaded
Open this post in threaded view
|

Re: Mystery of an Eq instance

Stuart A. Kurtz
Let me quibble.

> * Float and Double are imprecise types by their very nature. That's exactly what people are forgetting, and exactly what's causing misunderstandings.

Float and Double are precise types. What is imprecise is the correspondence between finite precision floating point types (which are common to all programming languages) and the mathematical real numbers. This imprecision is manifest in failures of the intended homomorphism from the reals to the floating point types.

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Mystery of an Eq instance

Bardur Arantsson-2
In reply to this post by Brandon Allbery
On 2013-09-20 18:31, Brandon Allbery wrote:
[--snip--]
> unless you have a very clever representation that can store
> in terms of some operation like sin(x) or ln(x).)

I may just be hallucinating, but I think this is called "describable
numbers", i.e. numbers which can described by some (finite) formula.

Not sure how useful they would be in practice, though :).

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Mystery of an Eq instance

Brandon Allbery
On Sat, Sep 21, 2013 at 12:35 PM, Bardur Arantsson <[hidden email]> wrote:
On 2013-09-20 18:31, Brandon Allbery wrote:
[--snip--]
> unless you have a very clever representation that can store
> in terms of some operation like sin(x) or ln(x).)

I may just be hallucinating, but I think this is called "describable
numbers", i.e. numbers which can described by some (finite) formula.

Not sure how useful they would be in practice, though :).

I was actually reaching toward a more symbolic representation, like what Mathematica uses.

--
brandon s allbery kf8nh                               sine nomine associates
[hidden email]                                  [hidden email]
unix, openafs, kerberos, infrastructure, xmonad        http://sinenomine.net

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Mystery of an Eq instance

David Thomas
Sure.  An interesting, if not terribly relevant, fact is that there are more irrational numbers that we *can't* represent the above way than that we can (IIRC).

However, those aren't actually interesting in solving the kinds of problems we want to solve with a programming language, so it's academic, and symbolic representation certainly gains you some things and costs you some things in meaningful engineering kinds of ways.


On Sat, Sep 21, 2013 at 9:41 AM, Brandon Allbery <[hidden email]> wrote:
On Sat, Sep 21, 2013 at 12:35 PM, Bardur Arantsson <[hidden email]> wrote:
On 2013-09-20 18:31, Brandon Allbery wrote:
[--snip--]
> unless you have a very clever representation that can store
> in terms of some operation like sin(x) or ln(x).)

I may just be hallucinating, but I think this is called "describable
numbers", i.e. numbers which can described by some (finite) formula.

Not sure how useful they would be in practice, though :).

I was actually reaching toward a more symbolic representation, like what Mathematica uses.

--
brandon s allbery kf8nh                               sine nomine associates
[hidden email]                                  [hidden email]
unix, openafs, kerberos, infrastructure, xmonad        http://sinenomine.net

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Mystery of an Eq instance

Brandon Allbery
On Sat, Sep 21, 2013 at 12:43 PM, David Thomas <[hidden email]> wrote:
Sure.  An interesting, if not terribly relevant, fact is that there are more irrational numbers that we *can't* represent the above way than that we can (IIRC).

I think that kinda follows from diagonalization... it does handle more cases than only using rationals, but pretty much by the Cantor diagonal argument there's an infinite (indeed uncountably) number of reals that cannot be captured by any such trick.

--
brandon s allbery kf8nh                               sine nomine associates
[hidden email]                                  [hidden email]
unix, openafs, kerberos, infrastructure, xmonad        http://sinenomine.net

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Mystery of an Eq instance

David Thomas
I think that's right, yeah.


On Sat, Sep 21, 2013 at 9:49 AM, Brandon Allbery <[hidden email]> wrote:
On Sat, Sep 21, 2013 at 12:43 PM, David Thomas <[hidden email]> wrote:
Sure.  An interesting, if not terribly relevant, fact is that there are more irrational numbers that we *can't* represent the above way than that we can (IIRC).

I think that kinda follows from diagonalization... it does handle more cases than only using rationals, but pretty much by the Cantor diagonal argument there's an infinite (indeed uncountably) number of reals that cannot be captured by any such trick.

--
brandon s allbery kf8nh                               sine nomine associates
[hidden email]                                  [hidden email]
unix, openafs, kerberos, infrastructure, xmonad        http://sinenomine.net


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Mystery of an Eq instance

Mike Meyer
In reply to this post by Bob Hutchison

On Sep 21, 2013 9:17 AM, "Bob Hutchison" <[hidden email]> wrote:
> On 2013-09-21, at 4:46 AM, Stijn van Drongelen <[hidden email]> wrote:
>> I do have to agree with Damodar Kulkarni that different laws imply different classes. However, this will break **a lot** of existing software.
> You could argue that the existing software is already broken.

I'd argue that it's not all broken, and you're breaking it all.

>> If we would do this, only Eq and Ord need to be duplicated, as they cause most of the problems. Qualified imports should suffice to differentiate between the two.
>>     import qualified Data.Eq.Approximate as A
>>     import qualified Data.Ord.Approximate as A
>>
>>     main = print $ 3.16227766016837956 A.== 3.16227766016837955
> As soon as you start doing computations with fp numbers things get much worse.

Exactly. The Eq and Ord instances aren't what's broken, at least when you're dealing with numbers (NaNs are another story). That there are pairs of non-zero numbers that when added result in one of the two numbers is broken. That addition isn't associative is broken. That expressions don't obey the substitution principle is broken. But you can't tell these things are broken until you start comparing values. Eq and Ord are just the messengers.


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Mystery of an Eq instance

Bardur Arantsson-2
On 2013-09-21 23:08, Mike Meyer wrote:
> Exactly. The Eq and Ord instances aren't what's broken, at least when
> you're dealing with numbers (NaNs are another story). That there are pairs

According to Haskell NaN *is* a number.

> Eq and Ord are just the messengers.

No. When we declare something an instance of Monad or Applicative (for
example), we expect(*) that thing to obey certain laws. Eq and Ord
instances for Float/Double do *not* obey the expected laws.

Regards,

/b

(*) Alas, in general, the compiler cannot prove these things, so we rely
on assertion or trust.


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Mystery of an Eq instance

Mike Meyer
On Sat, Sep 21, 2013 at 5:28 PM, Bardur Arantsson <[hidden email]> wrote:
> On 2013-09-21 23:08, Mike Meyer wrote:
> > Exactly. The Eq and Ord instances aren't what's broken, at least when
> > you're dealing with numbers (NaNs are another story). That there are pairs
> According to Haskell NaN *is* a number.

Trying to make something whose name is "Not A Number" act like a
number sounds broken from the start.

> > Eq and Ord are just the messengers.
> No. When we declare something an instance of Monad or Applicative (for
> example), we expect(*) that thing to obey certain laws. Eq and Ord
> instances for Float/Double do *not* obey the expected laws.

I just went back through the thread, and the only examples I could
find where that happened (as opposed to where floating point
calculations or literals resulted in unexpected values) was with
NaNs. Just out of curiosity, do you know of any that don't involve
NaNs?

Float violates the expected behavior of instances of - well, pretty
much everything it's an instance of. Even if you restrict yourself to
working with integer values that can be represented as floats.  If
we're going to start removing it as an instance for violating instance
expectations, we might as well take it out of the numeric stack (or
the language) completely.

    <mike


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Mystery of an Eq instance

Carter Schonwald
i had a longer email written out, but decided a shorter one is better.

I warmly point folks to use libs like the numbers package on hackage http://hackage.haskell.org/packages/archive/numbers/2009.8.9/doc/html/Data-Number-BigFloat.html

it has some great alternatives to standard floats and doubles.

the big caveat, however, is all your computations will be painfully slower by several orders of magnitude.  And sometimes thats a great tradeoff! but sometimes it isnt.  At the end of the day, you need to understand how to do math on the computer in a fashion that accepts that there is going to be finite precision. there is no alternative but to work with that understanding.

numbers on the computer have many forms. and many tradeoffs. there is no one true single best approach.

cheers
-Carter


On Sat, Sep 21, 2013 at 10:11 PM, Mike Meyer <[hidden email]> wrote:
On Sat, Sep 21, 2013 at 5:28 PM, Bardur Arantsson <[hidden email]> wrote:
> On 2013-09-21 23:08, Mike Meyer wrote:
> > Exactly. The Eq and Ord instances aren't what's broken, at least when
> > you're dealing with numbers (NaNs are another story). That there are pairs
> According to Haskell NaN *is* a number.

Trying to make something whose name is "Not A Number" act like a
number sounds broken from the start.

> > Eq and Ord are just the messengers.
> No. When we declare something an instance of Monad or Applicative (for
> example), we expect(*) that thing to obey certain laws. Eq and Ord
> instances for Float/Double do *not* obey the expected laws.

I just went back through the thread, and the only examples I could
find where that happened (as opposed to where floating point
calculations or literals resulted in unexpected values) was with
NaNs. Just out of curiosity, do you know of any that don't involve
NaNs?

Float violates the expected behavior of instances of - well, pretty
much everything it's an instance of. Even if you restrict yourself to
working with integer values that can be represented as floats.  If
we're going to start removing it as an instance for violating instance
expectations, we might as well take it out of the numeric stack (or
the language) completely.

    <mike


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe



_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Mystery of an Eq instance

Richard A. O'Keefe
In reply to this post by damodar kulkarni

On 20/09/2013, at 11:47 PM, damodar kulkarni wrote:

>
> There is an Eq instance defined for these types!
>
> So I tried this:
> *Main> sqrt (10.0) ==3.1622776601683795
> True
> *Main> sqrt (10.0) ==3.16227766016837956
> True
> *Main> sqrt (10.0) ==3.1622776601683795643
> True
> *Main> sqrt (10.0) ==3.16227766016837956435443343
> True
>
> It seems strange.

But *WHY*?   There is nothing in the least strange about this!
Did it occur to you to try

        3.1622776601683795 == 3.16227766016837956435443343

(Hint: the answer does not begin with "F".)

Four times you asked if the square root of 10 was equal to
a certain (identically valued but differently written) number,
and each time you got the same answer.  Had any of the answers
been different, that would have been shocking.

> So my doubts are:
> 1. I wonder how the Eq instance is defined in case of floating point types in Haskell?

At least for finite numbers, the answer is "compatibly with C, Fortran,
the IEEE standard, and every programming language on your machine that
supports floating point arithmetic using IEEE doubles."

> 2. Can the Eq instance for floating point types be considered "meaningful"? If yes, how?

Except for infinities and NaNs, yes.
As exact numerical equality.

When you get into infinities and NaNs, things get trickier,
but that's not at issue here.

It seems to me that you may for some reason be under the impression
that the 3.xxxx values you displayed have different values.  As
mathematical real numbers, they do.  But they all round to identically
the same numerical value in your computer.

> In general, programmers are **advised** not to base conditional branching on tests for **equality** of two floating point values.

At least not until they understand floating point arithmetic.

> 3. Is this particular behaviour GHC specific? (I am using GHC 6.12.1)

No.
>
> If there are references on this please share.

The IEEE floating point standard.
The LIA-1 standard.
The C99 and C11 standards.
"What every computer scientist should know about floating point arithmetic"
        -- citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.22.6768‎

Most of the unpleasant surprises people have with Haskell floating point
numbers are *floating point* surprises, not *Haskell* surprises.

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Mystery of an Eq instance

Sven Panne-2
In reply to this post by Mike Meyer
2013/9/22 Mike Meyer <[hidden email]>:
> On Sat, Sep 21, 2013 at 5:28 PM, Bardur Arantsson <[hidden email]>
> wrote:
> Trying to make something whose name is "Not A Number" act like a
> number sounds broken from the start.

The point here is that IEEE floats are actually more something like a
"Maybe Float", with various "Nothing"s, i.e. the infinities and NaNs,
which all propagate in a well-defined way. Basically a monad built
into your CPU's FP unit. ;-)

> I just went back through the thread, and the only examples I could
> find where that happened (as opposed to where floating point
> calculations or literals resulted in unexpected values) was with
> NaNs. Just out of curiosity, do you know of any that don't involve
> NaNs?

Well, with IEEE arithmetic almost nothing you learned in school about
math holds anymore. Apart from rounding errors, NaNs and infinities,
-0 is another "fun" part:

   x * (-1)

is not the same as

   0 - x

(Hint: Try with x == 0 and use recip on the result.)

> Float violates the expected behavior of instances of - well, pretty
> much everything it's an instance of. Even if you restrict yourself to
> working with integer values that can be represented as floats.  If
> we're going to start removing it as an instance for violating instance
> expectations, we might as well take it out of the numeric stack (or
> the language) completely.

Exactly, and I am sure 99.999% of all people wouldn't like that
removal. Learn IEEE arithmetic, hate it, and deal with it. Or use
something different, which is probably several magnitudes slower. :-/
_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Mystery of an Eq instance

Stijn van Drongelen
On Tue, Sep 24, 2013 at 5:39 PM, Sven Panne <[hidden email]> wrote:
2013/9/22 Mike Meyer <[hidden email]>:
> On Sat, Sep 21, 2013 at 5:28 PM, Bardur Arantsson <[hidden email]>
> wrote:
> Trying to make something whose name is "Not A Number" act like a
> number sounds broken from the start.

The point here is that IEEE floats are actually more something like a
"Maybe Float", with various "Nothing"s, i.e. the infinities and NaNs,
which all propagate in a well-defined way.

So, `Either IeeeFault Float`? ;)


_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Reply | Threaded
Open this post in threaded view
|

Re: Mystery of an Eq instance

John Lato-2
On Tue, Sep 24, 2013 at 11:36 AM, Stijn van Drongelen <[hidden email]> wrote:
On Tue, Sep 24, 2013 at 5:39 PM, Sven Panne <[hidden email]> wrote:
2013/9/22 Mike Meyer <[hidden email]>:
> On Sat, Sep 21, 2013 at 5:28 PM, Bardur Arantsson <[hidden email]>
> wrote:
> Trying to make something whose name is "Not A Number" act like a
> number sounds broken from the start.

The point here is that IEEE floats are actually more something like a
"Maybe Float", with various "Nothing"s, i.e. the infinities and NaNs,
which all propagate in a well-defined way.

So, `Either IeeeFault Float`? ;)

Sort of, but IeeeFault isn't really a zero.   Sometimes they can get back to a normal Float value:

  Prelude> let x = 1.0/0
  Prelude> x
  Infinity
  Prelude> 1/x
  0.0

Also, IEEE float support doesn't make sense as a library, it needs to be built into the compiler (ignoring extensible compiler support via the FFI).  The whole point of IEEE floats is that they're very fast, but in order to take advantage of that the compiler needs to know about them in order to use the proper CPU instructions.  Certainly you could emulate them in software, but then they'd no longer be fast, so there'd be no point to it.

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe
12