blog.poucet.org Rotating Header Image

January 28th, 2008:

A Fractional Type for Haskell

In this short blog post, I introduce a utility module that I will use in another blog post. To keep the content there short, I decided to make a blogpost just for this module. As usual, the license for this module is BSD, and the author is the author of this blog post.

Basically, while working on continued fractions, I needed a way to compare fractions of arbitrary numbers to see if their integral part coincided. Before I explain what I mean by that (if it’s not already obvious), I will first show some notation that I use to represent fraction types:

a :∼: b represents a fraction ab

Since this is a rather short post, let’s dive straight into the code.

As usual, this will be a literate haskell post, and it will include the full comments from the original file :) So first, the header, which also specifies some details regarding the workings of this code

> module Fraction where
> import Data.Ratio
>
> data Fraction a = {-# UNPACK #-}!a :~: {-# UNPACK #-}!a
> deriving (Show)
>
> infix 7 :~:

As mentioned earlier, this code serves to allow comparing of fractions for just their integral part. Unlike Data.Ratio in Haskell, this type allows for having 0 in the denominator. The reason for this is that the code that uses this type needed to be able to store these numbers and only later filter them. As such, we have the following rules (where nan = not a number):

  • ∀ a. (a > 0 ⇔ (a :∼: 0) = ∞) ∧ (a < 0 ⇔ (a :∼: 0) = −∞)
  • (0 :∼: 0) = nan
  • ∞ ≠ nan, −∞ ≠ nan, ∞ ≠ −∞, −∞ < ∞
  • ∀ a b: b ≠ 0 . (a :∼: b) ≠ nan ∧ (a :∼: b) ≠ ∞ ∧ (a :∼: b) ≠ −∞
  • ∀ a b: b ≠ 0 . −∞ < (a :∼: b) < ∞
  • ∀ a b c d: b ≠ 0 . (a :∼: b) = (c :∼: d) ⇔ a `div` b = c `div `d
  • ∀ a b c d: b ≠ 0 . (a :∼: b) < (c :∼: d) ⇔ a `div` b < c `div `d

It is important to notice that ‘nan’ can not be compared to any other value. It can only be ‘compared’ for equality, but it is not part of the order defined on these numbers. Porting the following rules straight to code, and adding some simple functions to check whether a number is infinite or a nan, and some accessors, we get:

> unFraction :: Fraction a -> (a,a)
> unFraction (a :~: b) = (a,b)
>
> toIntegral (a :~: b) = a `div` b
>
> isInfinite (a :~: 0) = a /= 0
> isInfinite _ = False
>
> isNan (0 :~: 0) = True
> isNan _ = False
>
> instance (Eq a, Num a, Integral a) => Eq (Fraction a) where
> -- (0 :~: 0) == (0 :~: 0) = True -- See blog-comments
> (0 :~: 0) == _ = False
> _ == (0 :~: 0) = False
> (a :~: 0) == (c :~: 0) = signum a == signum c
> (_ :~: 0) == (_ :~: _) = False
> (_ :~: _) == (_ :~: 0) = False
> (a :~: b) == (c :~: d) = a `div` b == c `div` d
>
> instance (Ord a, Num a, Integral a) => Ord (Fraction a) where
> (0 :~: 0) `compare` _ = error "Can not compare NaN's"
> _ `compare` (0 :~: 0) = error "Can not compare NaN's"
> (a :~: 0) `compare` (c :~: 0) = compare (signum a) (signum c)
> (a :~: 0) `compare` (_ :~: _) = compare a 0
> (_ :~: _) `compare` (c :~: 0) = compare 0 c
> (a :~: b) `compare` (c :~: d) = compare (a `div` b) (c `div` d)

Defining arithmethic for this type is rather easy. Since I only care about equality of the final number, we can use plain old arithmetic like any old rational type. This includes the instance for Fractional, which defines division. Finally, it is also rather easy to define an instance of Real number for this fractional type, since it’s very easy to generate a rational number from this. The only problem, of course, would be when ‘toRational’ is called on an infinite or a nan.

> instance (Num a, Integral a) => Num (Fraction a) where
> (a :~: b) + (c :~: d) = (a*d + b*c) :~: (b*d)
> (a :~: b) - (c :~: d) = (a*d - b*c) :~: (b*d)
> (a :~: b) * (c :~: d) = (a*c) :~: (b*d)
> negate (a :~: b) = (negate a :~: b)
> abs (a :~: b) = (abs a :~: abs b)
> signum (a :~: b) = (signum a :~: 1)
> fromInteger x = fromInteger x :~: 1
>
> instance (Fractional a, Integral a) => Fractional (Fraction a) where
> (a :~: b) / (c :~: d) = (a*d) :~: (b*c)
> fromRational x = (fromInteger . numerator$ x) :~: (fromInteger . denominator $ x)
>
> instance (Real a, Integral a) => Real (Fraction a) where
> toRational (a :~: b) = toRational a / toRational b

Well that’s all folks, not really complicated stuff. Just thought I’d add a light blog in preparation for the entry on continued fractions which will be reasonably math intensive.