Here’s a new Haskell WAT?!
Haskell has a type Rational for working with precisely-valued fractional numbers, and it models the mathematical concept of a rational number. Although it’s relatively slow compared with Double, it doesn’t suffer from the rounding that’s intrinsic to floating-point arithmetic. It’s very useful when writing tests because an exact result can be predicted ahead of time. For example, a computation that should produce zero will produce exactly zero rather than a small value within some range that would have to be determined.
Rational is actually a (monomorphic) specialization of the more general (polymorphic) type Ratio (from Data.Ratio). Ratio allows you to specify the underlying type used for the numerator and denominator. For example, to work with rational numbers using Int as the underlying type you can use Ratio Int. For the common case of using Integer as the underlying type, the type synonym Rational is provided:
type Rational = Ratio Integer
It’s tempting to use Ratio with a fixed-width type like Int because Int is much faster than Integer. However, let’s see what can happen if you do this:
λ> import Data.Int
λ> import Data.Ratio
λ> let r = 1 % 12 :: Rational in r - r == 0
True
λ> let r = 1 % 12 :: Ratio Int8 in r - r == 0
False
WAT?!
Let’s see what those subtracted values evaluate to:
λ> let r = 1 % 12 :: Rational in r - r
0 % 1
λ> let r = 1 % 12 :: Ratio Int8 in r - r
0 % (-1)
Hmmm, let’s see if that Ratio Int8 value is considered equal to 0:
λ> let r = 0 % (-1) :: Ratio Int8 in r == 0
True
WAT?!
Let’s see what those manually-entered values are:
λ> 0 % (-1) :: Ratio Int8
0 % 1
λ> 0 :: Ratio Int8
0 % 1
OK, so these values really are equal, but why are the values in the subtraction different? The explanation is two-fold.
First, 0 % (-1) is a denormalized state for Ratio and shouldn’t occur. (As you’ve probably suspected, it arises from integer overflow. More on that in a minute.) It’s not too surprising, then, that it isn’t equal to 0.
But why is it equal to 0 when we enter it directly? It’s because % is a function not a constructor, and it normalizes the signs of the numerator and denominator before constructing the value:
x % y = reduce (x * signum y) (abs y)
The underlying assumption (the invariant) is that denominators will always be positive.
reduce is a function that reduces the numerator and denominator to their lowest terms, by dividing by the greatest common divisor:
reduce x y = (x `quot` d) :% (y `quot` d)
where d = gcd x y
Here you can see the constructor that actually creates the values from their components, which is :%. It’s not exported from Data.Ratio and the “smart constructor” % is used instead, to ensure that new Ratio values always satisfy the invariant.
Second, addition and subtraction are implemented without trying to minimize the possibility of integer overflow. For example:
(x :% y) - (x' :% y') = reduce (x * y' - x' * y) (y * y')
If y * y' overflows to a negative value, reduce will not normalize the signs. The result of gcd is always non-negative so the signs don’t change and denormalized values are never renormalized. That happens only in % when constructing Ratio values.
Let’s look at what happens in our example:
λ> x = 1; y = 12; x' = 1; y' = 12
λ> x * y' - x' * y :: Int8
0
λ> y * y' :: Int8
-112
λ> gcd 0 (-112)
112
λ> 0 `quot` 112
0
λ> (-112) `quot` 112
-1
The reduced result of 1 % 12 - 1 % 12 is therefore the denormalized value 0 :% (-1) which isn’t considered equal to the normalized value 0 % 1.
Even though 12 is much less than maxBound :: Int8, when squared it results in integer overflow. The implementation of Num for Ratio is not designed to avoid overflows and they can happen very easily with numerators and denominators that are much less than the maxBound for the type.
The implementation could have used a slightly different approach:
(x :% y) - (x' :% y') = reduce (x * z' - x' * z) (y * z')
where z = y `quot` d
z' = y' `quot` d
d = gcd y y'
However, the use of reduce is still necessary (consider 3 % 10 - 2 % 15) so this requires two more divisions and a gcd compared with the actual implementation.
Using a type as small as Int8 might seem a little unrealistic, but the problem can occur with any fixed-width integral type and I used Int8 for the illustration because it’s easier to understand the problem when working with small values. I originally encountered it when using Ratio Int even though Int has a very large maxBound. I was writing property tests using QuickCheck for some polymorphic arithmetic code that was supposed to produce a zero sum as a result. The test succeeded with Rational and failed with Ratio Int and I couldn’t understand why because the random values being generated by the test framework had numerators and denominators far less than maxBound :: Int. However, they were greater than its square root.
The documentation for Ratio says:
Note that Ratio’s instances inherit the deficiencies from the type parameter’s. For example,
Ratio Natural‘sNuminstance has similar problems toNatural‘s.
However, that doesn’t really prepare you for what might happen with other type parameters! The moral of this story is that Ratio isn’t much use on its own and you should always use Rational unless you really understand what you’re getting into.
Like that blog post? Check out the Haskell section of our site with tutorials and other blog posts. You can also check out all Haskell tagged blog posts.
We’re hiring. Interested in working with our team on solving these kinds of WAT issues? Check out our jobs page for more information.
Subscribe to our blog via email
Email subscriptions come from our Atom feed and are handled by Blogtrottr. You will only receive notifications of blog posts, and can unsubscribe any time.