Why does Haskell implement Enum on the Real?

user_16524361 0
Viewed 179

The Enum typeclass implies that the implementing types can be ordered in some meaningful way. In Haskell, the Real type implements Enum. Coming from a mathematics background, this is very strange. A hundred years ago, Georg Cantor proved that reals cannot not be indexed, that is, there is no way to say what is the n-th real for all reals.

Now, concrete types such as Double do in fact have a finite domain. So you could argue that they can implement Enum. One would assume the the successor of a Double would be the next valid Double. Instead, it is simply the addition of 1. Hence, we see weirdness like:

Prelude> succ (1e20 :: Double) == (1e20 :: Double)
True

In my opinion, this behavior breaks the usefulness of Enum. Can anyone explain the reasoning behind this?

Edit: Corrected Ord to Enum and clarified that reals are not aleph zero.

Post-Script: This comment illumined the answer to me:

Enum Double is nowadays considered a mistake by several Haskellers. It was added to allow e.g. [1.0 .. 20.0] to count with a step of one unit. That required succ to be (+1) instead of the true "next" double. Also, it opens a can of worms since length [1.0 .. 99.5] might be 99 or 100 depending on rounding errors. Worse, this can't be fixed, it's inherently fragile.

haskell
2 Answers

As Robin Zigmond commented, you're confusing the Ord and Enum classes. Ord is what's a superclass of Real, but Enum is what succ belongs to.

Ord does not allow you to enumerate, or otherwise generate any elements of a type, it only allows you to compare given elements. And being able to check whether x < y for two real numbers would seem perfectly straightforward and uncontroversial.†

By contrast, the Enum class is an absolute mathematical mess. This is not a class for enumerating all values of a type (that would be Universe), rather you should just think of it as the class that can be used for list builders of the form [1, 1.5, .. 9] or ['q'..]. These don't really have any clear mathematical interpretation, they're just useful for writing concise practical code.

It has been argued that Float and Double should not have Enum instances. But IMO those instances are ok in as far as the class itself is ok – not good, but not bad enough to warrant the hassle of replacing it with something new (and braking lots of existing code that makes use of list comprehensions).

†Actually, this is worth some consideration. Unlike x < y, which is generally a perfectly fine thing to check, x==y is actually problematic in some ways, both mathematically for exact reals and practically for floating-point numbers. Speaking constructive-mathematically, all you can do is check in finite time that x < y or x > y, but you can never be sure that two values are equal. And for floating-point numbers, you should never assume that two values are ==-equal even if they come out of mathematically equivalent comparisons. Instead, what you should do in testing is to check that x-ε < y < x+ε for some small ε. (How small is appropriate can be tricky to determine.)

user_7459030

I'm not a mathematician, but my understanding is that real numbers can be ordered, they just can't be well-ordered.

The Ord class in Haskell basically just says that for any two elements of the type, you can distinguish whether one is less than, greater than, or equal to the other. Mathematical real numbers support this with the usual ≤ and ≥ relationships.

However the usual order on real numbers is not a well-order, which would require that every non-empty subset of the reals would have a least element. The Haskell class Ord says nothing about finding least elements for arbitrary subsets (or anything equivalent), so there's no problem with a type that purports to represent real numbers being in Ord.

When you talk about succ, you're asking about the Enum type class. That has nothing to do with Ord1.

The Enum class is often considered a wart in the language. The few laws it documents actually mandate that its implementations should not be total2. It defines enumerability by ability to be translated to/from Int, which is fundamentally finite while also being too large for any user-defined finite type to have a total toEnum. It is not a good representation of the mathematical concept of an enumerable set. I don't think Enum would end up the way it is if the standard library were being invented from scratch now.

What Enum does do is support Haskell's [n..m] syntax. This is why it made sense for non-integral number types like Double to have succ x = x + 1 instead of attempting to find the next representable number. The spec wants [1..3] :: [Double] to be [1.0, 2.0, 3.0], not a list of every representable number between 1 and 3.

So Double having an Enum instance just isn't a very sensible idea from a pure mathematics point of view (with the Enum we have), and neither is the whole Enum class itself, but they aren't really intended to be either; pure mathematics wasn't what motivated their creation. If you want to think of Doubles as representing mathematical reals then Enum is just a wart you have to remember to avoid (but also, that is far from your only problem with thinking of Doubles as reals). There isn't really a hugely satisfying answer to your question. Not everything in Haskell is perfect representation of mathematical concepts.

1 Other than perhaps an implied law that if the type is also in Ord then x < succ x should hold whenever succ x is defined? It's not actually stated as a law, and Enum is a pretty ad-hoc class, it's arguable either way, but I'd be a bit disappointed in an instance that didn't satisfy that.

2 From the docs:

For any type that is an instance of class Bounded as well as Enum, the following should hold:

  • The calls succ maxBound and pred minBound should result in a runtime error.
  • fromEnum and toEnum should give a runtime error if the result value is not representable in the result type. For example, toEnum 7 :: Bool is an error.
user_4501280
Related