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 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 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
λ> let r = 1 % 12 :: Ratio Int8 in r - r == 0
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
λ> let r = 0 % (-1) :: Ratio Int8 in r == 0
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.
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
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')
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
Let's look at what happens in our example:
λ> x = 1; y = 12; x' = 1; y' = 12
λ> x * y' - x' * y :: Int8
λ> y * y' :: Int8
λ> gcd 0 (-112)
λ> 0 `quot` 112
λ> (-112) `quot` 112
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.
12 is much less than
maxBound :: Int8, when squared it results in integer overflow. The implementation of
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
Note that Ratio's instances inherit the deficiencies from the type parameter's.
Num instance has similar problems to
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.
Do you like this blog post and need help with Next Generation Software Engineering, DevSecOps or Blockchain & Smart Contracts? Contact us.