Add `Bounded` instances for Double, Float, CDouble and CFloat

[AliceRixte]

Motivation

Edited TL;DR

Floats can be seen as a representation of extended reals. In that regard, they are bounded between -∞ and +∞. When seeing -1/0 as a representation of -∞ and 1/0 as a representation of +∞, we get a bounded instance for floats.

Initial motivation

Having a Bounded instance for Double is generally useful as soon as one uses 1/0 and -1/0 to represent infinity. For instance , it allows to represent whole intervals (see ekmett/intervals#27 or msakai/data-interval#46)

This was previously discussed here. This Stack Overflow answer suggests the following explanation as to why those instances do not exist :

 >>> let nan = 0/0; infinity = 1/0 in (nan > infinity, infinity > nan)
(False,False)

which means that 1/0 and -1/0 are not actual bounds.

However, the exact same argument can be used to say that there should not even be an Ord instance in a first place, as this means that Double is not totally ordered.

Proposal

Add the following instances to base :

instance Bounded Double where
  minBound = negate (1/0)
  maxBound = 1/0

instance Bounded Float where
  minBound = negate (1/0)
  maxBound = 1/0

as well as the corresponding derived instances for CFloat and CDouble.

---

• GHC ticket

---

Disclaimer

I'm completely new to the CLC process. I'm willing to implement this, but I will probably need guidance, which I would be very grateful for.

[jeltsch]

Could you perhaps summarize the context a bit, in particular saying why Bounded instances for Float and Double would be useful?

My impression is that there would be no inherent problem with those instances as such. The problems that you mention regarding the interplay of them with the Ord instances of Float and Double would in fact be caused by those Ord instances being bogus. I think that those Ord instances should better let comparisons with NaN fail instead of letting them return False. Well, this still wouldn’t be a really convincing solution, and there probably cannot be any: IEEE floating point numbers are just a catastrophe from a mathematical point of view.

[AliceRixte]

Could you perhaps summarize the context a bit, in particular saying why Bounded instances for Float and Double would be useful?

Sure ! One simple real life use case comes from Kmett's intervals library which defines intervals as

data Interval a = I !a !a | Empty

then how to define the whole interval that contains every number in a ?

For now, it is defined as

whole :: Fractional a => Interval a
whole = I (-1/0) (1/0)

But this is quite wrong, because we get whole intervals for types for which it does not make sense (e.g. Complex) and we do not get whole for type for which it would make sense, (e.g. Int, or even Bool).

Instead, we want to write

whole :: Bounded a => Interval a
whole = I minBound maxBound

---

Most other examples I can think about are variants of the above. For instance, I found myself needing a Bounded instance for Double when computing the codomain of a monotonic, continuous function :

monotonicCodomain :: Bounded a => (a -> b) -> (b, b)
monotonicCodomain f = (f minBound, f maxBound)

[jeltsch]

Are the bounds passed to the I constructor of Interval considered included in or excluded from the interval? My guess is that they are meant to be included. However, specifying the interval of all real numbers by giving included bounds is simply not possible, as this interval is open. Constructing it as I (-1/0) (1/0) or equivalently I minBound maxBound with the Bounded instances you propose gives you not the interval of all real numbers but that of all real numbers and additionally −∞ and ∞. There might be a largest and smallest real number representable by Float or Double, and using these would give you the interval of all representable real numbers then, but using these numbers as minBound and maxBound wouldn’t be a good idea, as negative and positive infinity are still there.

[AliceRixte]

TL;DR

My main point is that it is useful to have an efficient representation for extended reals. Floats are such a representation.

Having a Bounded instance for floats allow using extended reals polymorphically in a more general and principled way than RealFloat does (one wants to be able to declare intervals of Int).

Properly modeling infinities yields slower code, for no useful reason.

---

Are the bounds passed to the I constructor of Interval considered included in or excluded from the interval?

They are included.

However, specifying the interval of all real numbers by giving included bounds is simply not possible, as this interval is open.

While this is true for $\mathbb{R}$, it is not for extended reals $\overline{\mathbb{R}}$. Here I'm seeing floats as a model of extended reals, not for reals. One could argue that floats are a terrible model for extended reals and I would not disagree. But similarly floats are also a terrible model for reals, and we still get things done with them.

To properly define infinities, one could use the extended-reals package, that defines Extended as

data Extended r
  = NegInf    -- ^ negative infinity (-∞)
  | Finite !r -- ^ finite value
  | PosInf    -- ^ positive infinity (+∞)

and then use Interval (Extended Double) which has a bounded instance, but what would we gain except slowing things down ? Instead of having three edge values (1/0, (-1/0) and 0/0) that do not behave properly, we gained two additional ones, as the Num instance fails for some values :

  Finite a + Finite b = Finite (a+b)
  PosInf + NegInf = error "PosInf + NegInf is undefined"
  NegInf + PosInf = error "NegInf + PosInf is undefined"
  PosInf + _ = PosInf
  _ + PosInf = PosInf
  NegInf + _ = NegInf
  _ + NegInf = NegInf

So in the end, by trying to model infinity properly, we end up with errors instead of NaN, and a code that is likely to be slower, and take up more memory, for no additional gain.

---

Now I have to mention that Masahiro Sakai's data-interval handles that in a quite elegant way, by defining intervals as

data Interval r
  = Whole
  | Empty
  | Point !r
  | LessThan !r
  | LessOrEqual !r
  | GreaterThan !r
  | GreaterOrEqual !r
  -- For constructors below
  -- the first argument is strictly less than the second one
  | BothClosed !r !r
  | LeftOpen !r !r
  | RightOpen !r !r
  | BothOpen !r !r

Bounds can then be accessed via

lowerBound' :: Interval r -> (Extended r, Boundary)
lowerBound' = \case
  Whole            -> (NegInf,   Open)
  Empty            -> (PosInf,   Open)
  Point r          -> (Finite r, Closed)
  ...

But then, we constantly have to pattern match the Extended bounds every time we want to make some comparison with a float. So while we gain some type safety, we do lose efficiency, which can be best achieved by seeing intervals as mere pairs.

[jeltsch]

Alright, so you see Float and Double not as approximations of the reals (ℝ) but of the extended reals (ℝ ∪ {−∞, +∞}). That’s a sensible view, and with this view introducing Bounded instances that specify −∞ and +∞ as minBound and maxBound makes perfect sense. I cannot judge whether viewing IEEE floating point types as extended reals is appropriate for your application areas, but it is at least pretty appropriate in general. With this in mind, I’m in favor of adding those Bounded instances.

[TeofilC]

The next step here is to create a GHC MR. Take a look at https://gitlab.haskell.org/ghc/ghc/-/wikis/contributing#newcomers-to-ghc or https://ghc.dev if you haven't contributed before. (I can help in person at ZuriHac if you are going)

You'll want to add the instances to the files where these types are defined, eg, https://gitlab.haskell.org/ghc/ghc/-/blob/master/libraries/ghc-internal/src/GHC/Internal/Float.hs

As you are just adding instances, this can only break existing code if users have written orphan instances. It seems that the following packages have written orphan instances:

• Etage-Graph
• wavy
• Gamgine

Note that subhask defines its own Bounded type with the same definition as what you gave. Most orphan instances also use the same definition, except for Gamgine which has:

maxFloat :: RealFloat a => a -> a
maxFloat a = encodeFloat m n
   where
      b = floatRadix a
      e = floatDigits a
      (_, e') = floatRange a
      m = b ^ e - 1
      n = e' - e

instance Bounded Double where
   maxBound = maxFloat (0 :: Double)
   minBound = -maxBound

It's unclear to me if that is equivalent.

I imagine the breakage from this change would be small.

It seems like a sensible change to me!

[Bodigrim]

Could you perhaps summarize the context a bit, in particular saying why Bounded instances for Float and Double would be useful?

Here are a few examples, which this proposal will fix:

> import Data.Semigroup
ghci> getMax $ foldMap Max [3,42,15] :: Int
42
ghci> getMax $ foldMap Max [3,42,15] :: Double
<interactive>:5:10: error: [GHC-39999]
    • No instance for ‘Bounded Double’ arising from a use of ‘foldMap’

> import Data.Ord
> [Down 5 .. Down 1] :: [Down Int]
[Down 5,Down 4,Down 3,Down 2,Down 1]
ghci> [Down 5 .. Down 1] :: [Down Double]
<interactive>:9:1: error: [GHC-39999]
    • No instance for ‘Bounded Double’

---

It seems that the following packages have written orphan instances:

• Etage-Graph
• wavy
• Gamgine

Neither of them is on Stackage, so I assume an impact assessment with https://github.com/haskell/clc-stackage will flag no issues.

[AliceRixte]

@TeofilC

The next step here is to create a GHC MR. Take a look at https://gitlab.haskell.org/ghc/ghc/-/wikis/contributing#newcomers-to-ghc or https://ghc.dev if you haven't contributed before. (I can help in person at ZuriHac if you are going)

Thank you for your explanation, it helped a lot. I won't be in ZuriHac, sadly, but thank you for offering.

[AliceRixte]

I opened both a GHC ticket and a GHC MR.

Declaring instances for CDouble and CFloat is pretty awkward. I had to go and modify some C macros and I'm actually unsure whether I did that right (it does yield the expected results in GHCi though), which is why I marked the MR as draft.

The whole file ghc-internals/include/CTypes.h confuses me :

1. Grepping for FLOATING_TYPE_WITH_CTYPE yields no result in the whole GHC code base, so I think this is dead code.
2. There is a comment saying

   As long as there is no automatic derivation of classes for newtypes we resort
   // to extremely dirty cpp-hackery.

followed by another comment saying the exact contrary (or maybe there is something I don't undertand ?)

GHC can derive any class for a newtype, so we make use of that here...

[jeltsch]

@AliceRixte, I guess it’d be good to point these things out in a comment to your merge request, so that in particular reviewers will have a closer look at your corresponding changes.

[rickowens]

I do not believe that IEEE floating point number form a bounded poset do they, because of NaN?

I am worried that treating IEEE Float as an idealized extended reals (ℝ ∪ {−∞, +∞}) and ignoring what it actually is from a programming perspective (ℝ ∪ {−∞, +∞} ∪ {NaN}) might generally cause more harm than good. I think I would like to rely, for instance on a property test that claims minBound <= a, for all possible values of a.

[ChickenProp]

If we could remove Eq and Ord from these types I'd be very tempted go for that. (IIUC Rust has PartialEq and PartialOrd, does anyone know how it works for them?) But that's obviously not viable.

Given that we treat them as extended-reals for those classes, it doesn't feel to me like adding Bounded makes things much worse. Slightly worse, admittedly. But IMO the uses give here are strong enough to be worth it.

[rickowens]

Well, I definitely sympathize with Eq and Ord. In the absence of a widely used or standardized PartialEq or PartialOrd, floats would be would be nigh on useless if you couldn't compare them.

While ignoring NaN in Bounded falls into the same category of pragmatism as ignoring it in Eq and Ord, I'm not sure it provides anywhere near the same degree of pragmatism as for Eq and Ord.

My sense is that we've historically built ourselves a number of foot guns by being a little less principled for a little more convenience. And the trend these days is to try to revert that. Like, for instance, people complaining of all the partial functions in Prelude. At the time, I'm sure it seemed like, "It's such a chore to force me to pattern match my call to head on Maybe when I know this list is not empty" was a perfectly reasonable argument at that time.

To your point though, I agree, it does not seem like this has anywhere near the same degree of risk as some of those examples. So the stakes aren't nearly so high as all that. But it still feels a bit unsettling IMO, like we'll end up on the wrong side of history somehow.

Looking at this from another perspective: For the motivating example given here, the first thing I would do when writing code for my day job would be to reify the polymorphic type to a concrete type that's appropriate for whatever business logic I'm coding.

let
  startInterval = whole @Float
in
  aBunchOfOperationsOn startInterval

For this case, I don't think I would be particularly inconvenienced if I were to have to write

let
  startInterval = wholefloatInterval
in
  aBunchOfOperationsOn startInterval

instead.

The difference between this and the situation with Eq and Ord is that aBunchOfOperationsOn is likely to require a lot of calls to Eq and Ord methods (and Num methods while we're at it), but is probably unlikely to require a bunch of calls to Bounded methods.

[rickowens]

Having a Bounded instance for Double is generally useful as soon as one uses 1/0 and -1/0 to represent infinity.

I'm somewhat surprised that there doesn't seem to be posInfinity or negInfinity functions exposed in base.