Overloading Haskell numbers, part 3, Fixed Precision. Fixed precision numbers can be handy to have sometimes. Haskell only provides integral, rational, and floating point in the Prelude, but I want more! I want to define a type of fixed precision numbers, i.e., numbers that have a certain number of decimals. Rational numbers are handy to represent these numbers so here we go.

newtype Fixed = F Rational deriving (Eq, Ord, Enum, Num, Fractional, Real, RealFrac)

This uses an GHC extension that allows you to derive anything from the representation type so we don't have to define all those tedious instances. But wait, where is the fixed precision? What I just defined is just the Rational numbers with a different name. I really want a type which is parametrized over what precision it has. OK, so here we go again:

newtype Fixed e = F Rational deriving (Eq, Ord, Enum, Num, Fractional, Real, RealFrac)

Here e is meant to be a type that specifies the precision. Let's capture those types that we allow as the precision as a type class:

class Epsilon e where
    eps :: e -> Rational

The idea here is that the actual argument to the eps function is not used, it's just a proxy and the type carries all the information. Here's an example:

data Eps1
instance Epsilon Eps1 where
    eps _ = 1

The eps returns 1 for the Eps1 type. So the intended meaning is that the type Fixed Eps1 are numbers within an epsilon of the right answer, and epsilon is 1. Similarly

data Prec50
instance Epsilon Prec50 where
    eps _ = 1e-50

The type Fixed Prec50 has an epsilon of 1e-50, i.e., 50 decimals. Btw, notice that what looks like a floating point literal is actually a rational number; one of the very clever decisions in the original Haskell design. We can also define type constructors like

data EpsDiv10 p
instance (Epsilon e) => Epsilon (EpsDiv10 e) where
    eps e = eps (un e) / 10
       where un :: EpsDiv10 e -> e
             un = undefined

The type Fixed (EpsDiv10 Prec50) has an epsilon of 1e-50/10 = 1e-51. Note how the function un is just a dummy to get the e. If we had used the scoped type variable extension we could have avoided this function. OK, so we can compute with these fixed precision numbers, but where does the epsilon enter? Nowhere, so far. All arithmetic is performed exactly by the rationals, but our first use of the epsilon is in the show function.

instance (Epsilon e) => Show (Fixed e) where
    showsPrec = showSigned showFixed
      where showFixed f@(F x) = showString $ show q ++ "." ++ decimals r (eps $ un f)
              where q :: Integer
             (q, r) = properFraction x
      un :: Fixed e -> e
             un = undefined
             decimals a e | e >= 1 = ""
                          | otherwise = intToDigit b : decimals c (10 * e)
                 where (b, c) = properFraction (10 * a)

To print a fixed point number we first print the integer part. The properFraction method handily returns the integer part and some left over fraction that is <1. We then print decimal after decimal by multiplying the fraction by 10, converting the integer part to a digit, and then recursing. While generating these decimals we also multiply the epsilon by 10 each time and stop printing when epsilon is >= 1, because then we don't need any more decimals. All right, lets put it to the test:

Data.Number.Fixed> 1/3 :: Fixed Prec50
0.33333333333333333333333333333333333333333333333333
Data.Number.Fixed> 3/8 :: Fixed Prec10
0.3750000000
Data.Number.Fixed> (1 :: Fixed Prec10) + (0.5 :: Fixed Prec50)
    Couldn't match expected type `Prec10'
           against inferred type `Prec50'
      Expected type: Fixed Prec10
      Inferred type: Fixed Prec50

As we want, we can't mix different fixed point numbers with different precisions. Sometimes we do want to convert, so let's provide such a function

convertFixed :: Fixed e -> Fixed f
convertFixed (F x) = F x

It looks like this function does nothing, and it's true. It just converts the type, and since the epsilon type is not involved in the number itself it's trivial. Well, basic arithmetic isn't that much fun. What about the transcendental functions? Luckily Jan Skibinski has already implemented all of them. They compute the various function to with an epsilon using continued fractions. The instance declaration looks something like:

instance (Epsilon e) => Floating (Fixed e) where
    sqrt = toFixed1 F.sqrt
    exp = toFixed1 F.exp
    ...

toFixed1 :: (Epsilon e) => (Rational -> Rational -> Rational) -> Fixed e -> Fixed e
toFixed1 f x@(F r) = F (f (eps (un x)) r)
  where un :: Fixed e -> e
        un = undefined

And all the clever code I stole from Jan is in the module F, see link below. Now it's getting more fun.

Data.Number.Fixed> pi :: Fixed Prec50
3.14159265358979323846264338327950288419716939937510
Data.Number.Fixed> exp 10 :: Fixed Prec10
22026.4657881843
Data.Number.Fixed> log 2 :: Fixed Prec50
0.69314718055994530941723212145817656807550013436026
Data.Number.Fixed> exp (sin (sqrt (54/42))) :: Fixed Prec10
2.4745696343
Data.Number.Fixed> sqrt 2 :: Fixed Prec500
1.41421356237309504880168872420969807856967187537694807317667973799073247
8462107038850387534327641572735013846230912297024924836055850737212644121
4970999358314132226659275055927557999505011527820605714701095599716059702
7453459686201472851741864088919860955232923048430871432145083976260362799
5251407989687253396546331808829640620615258352395054745750287759961729835
5752203375318570113543746034084988471603868999706990048150305440277903164
5424782306849293691862158057846311159666871301301561856898723724

Data.Number.Fixed Data.Complex> let i = 0 :+ 1 :: Complex (Fixed Prec50) 
Data.Number.Fixed Data.Complex> exp (i*pi)
(-0.99999999999999999999999999999999999999999999999999) :+ 0.00000000000000000000000000000000000000000000000000

Naturally, we need to package up all these definitions in a module that will keep the Fixed type abstract, and you can also keep the Epsilon class and the various Epsilon types abstract if you provide enough building blocks. Source at http://www.augustsson.net/Darcs/Data.Number/.