Implementing a fractional data type and investigating the expansion of the square root of 2
A couple of weeks ago, I completed Project Euler #57: Investigating the Expansion of the Square Root of 2. I found the problem really interesting, since it required me to write up my own fractional operations (addition, division, etc.)
Today, I decided that I wanted to take my minimally defined fractional library and make it a more full-featured one. First, I’ll first walk through the building of the data type and implementing fractional operations, and then I’ll get to my solution of the Project Euler problem.
First thing’s first. A
Fraction is defined as a numerator and a denominator. My fractions consist of only Integers, and here’s how the data type is defined:
data Fraction = Frac Integer Integer -- Numerator Denominator instance Show Fraction where show (Frac a b) = (show a) ++ " / " ++ (show b)
I wanted fractions to show up in the form
x / y, so that is what the instance of
Show I defined does. So, now that we have a data type, what can we do with it?
Here’s a list of common functions that I think are necessary in the definition of a fraction: Addition, Subtraction, Multiplication, Division, Exponentiation, Simplification, Negation, getting the Numerator, and getting the Denominator. Let’s start with the simple ones:
num :: Fraction -> Integer num (Frac a _) = a denom :: Fraction -> Integer denom (Frac _ b) = b
Those are are
denominator functions. We simply take the first or second argument of the
Frac in order to get the parameter that we need, and disregard the other one (using
_) since it’s unused. Simplifying is also simple enough. We just need to divide the numerator and the denominator by the greatest common divisor of the two. Since Haskell gives us a
GCD function, this is pretty darn simple.
Here’s how it’s implemented:
simplify :: Fraction -> Fraction simplify (Frac a b) = Frac (a `quot` factor) (b `quot` factor) where factor = gcd a b
Easy! We just make a new fraction out of the divided values. The function
quot is basically just integer division that truncates the result towards 0. The second half of that is unimportant in this instance, since we’re dividing by the
GCD of the numbers and the result will always be an integer value. Okay, so we have a couple of functions. Great! But, what about implementing addition, subtraction, etc?
Well, basically what we want to do here is define a couple of instances of numeric types for our Fractional data type. The first instance we need to derive is
Num, which has a few operations that we want:
instance Num Fraction where (-) f (Frac a b) = f + (Frac (-a) b) (+) (Frac a b) (Frac c d) = Frac num denom where denom = lcm b d num = a * (denom `quot` b) + c * (denom `quot` d) (*) (Frac a b) (Frac c d) = Frac (a*c) (b*d) negate (Frac a b) = Frac (-a) b abs f = fmapF abs f where fmapF f (Frac a b) = Frac (f a) (f b) fromInteger x = Frac x 1 signum (Frac a b) = if a == 0 then 0 else if b > 0 then if a < 0 then (-1) else 1 else if a < 0 then 1 else (-1)
The three “common” operators (
*) are defined here, which means that we can now evaluate expressions such as
Frac 1 2 * Frac 1 2. Cool, right? Those three operations are fairly self-explanatory, and the code (hopefully) isn’t too tough to follow. There are also three other function definitions here, that maybe aren’t quite as clear. The function
negate simply turns a negative fraction positive, or a positive fraction negative. The function
abs takes the absolute value of the fraction. This is fairly simple; we just use a function that maps
abs (Integer absolute value) over the numerator and denominator of the fraction. The last is
signum, which looks probably the most complicated, but all it actually does is tells us whether the
Fractionis less than, greater than, or equal to 0 (returning -1, 1, and 0, respectively). Cool, so since we got all of those functions out of
Num, where can we find the rest? We’re missing
/, so we’ll make our
Fraction an instance of
Fractional. Seems appropriate, right?
instance Fractional Fraction where (/) f = (*) f . recip recip (Frac a b) = Frac b a fromRational r = Frac (numerator r) (denominator r)
Cool, we get division out of that, which is simple enough! We just take the reciprocal of the second fraction, and multiply the two. This may look a little funky, so I’ll explain that last. The other two functions defined here are
recip simply flips the numerator and denominator in a
Fraction, and this is easily handled with pattern matching.
fromRational takes a rational number (which is provided the
denominator functions) and turns it into a
Fraction. Knowing what the
denominator functions are, this function is incredibly trivial.
Okay, so about that division function. Our division appears to take only one argument, but it actually takes two.
(*) f f' is just syntactic sugar for
f * f'. We want to compose the function
f with the function
recip f', so we use the function
(*), apply it to
f, and then apply that to the function
recip, which is then called on the second argument of the function.
Alright! We’ve got plenty of functions at our disposal now, so what’s next? Well, we want to be able to compare
Fractions, so let’s go ahead and make it an instance of
Ord, which allow us to check equivalency and order, respectively.
instance Eq Fraction where (/=) f = not . (==) f (==) f f' = (x == x') && (y == y') where (Frac x y) = simplify f (Frac x' y') = simplify f' instance Ord Fraction where compare (Frac a b) (Frac c d) = compare (a `quot` b) (c `quot` d) (<) f = (==) LT . compare f (>) f = (==) GT . compare f (>=) f = not . (<) f (<=) f = not . (>) f max f f' = if f < f' then f' else f min f f' = if f < f' then f else f'
There’s a lot of functions that are similar in structure to our
/ function from earlier, so understanding what is happening with those will make these much easier to understand. Starting with
Eq, we have two functions,
/= (not equals) and
== simply checks to see if the simplified version of
f and the simplified version of
f' have the same numerators and denominators.
/= basically just returns the opposite of
== by calling
not on the result.
Ord isn’t too tough either.
First we have
compare, which returns a comparator (
EQ) based on the relationship between two
Fractions. The inequality functions are all designed around this function. The
min functions are simple, and designed around our inequality functions. So, what’s left? I decided I wanted to experiment, so I decided to also make
Fraction an instance of Monoid and give `Fraction` a simpler constructor. Here’s the rest!
instance Monoid Fraction where mempty = 0 mappend = (+) mconcat = foldr mappend mempty (%) :: Integer -> Integer -> Fraction (%) a = simplify . Frac a
The instance of
Monoid defines a couple of functions:
mempty is the minimal value for the
Monoid.I chose 0 (which gets automatically boxed into a
mappend is a combiner function, and I thought that addition of fractions fit this bill well enough, so I simply gave it an alias.
mconcat concatenates a list of fractions with some function, and in our case, sums the entire list. Our type constructor (
%) takes two integers and boxes them up into a
Fraction, which is then simplified. Easy enough. One final note on all of this. You may have noticed that exponentiation (
^) isn’t implemented here. But, it actually is! Turns out, any data type that has a
Num instance defined (like our
Fraction) can use the
^ operator. So things like
(1 % 2)^2 actually get evaluated properly. (In this case, to
1 % 4).
All right! Let’s use this small library to solve Project Euler #57! Knowing how to use the
Fraction library, this should be relatively easy to follow. Here we go:
import Fraction main = return . length . filter moreInNum . map sqrtTwo $ [1..1000] where moreInNum f = length ( (show . num) f ) > length ( (show . denom) f) sqrtTwo = simplify . (+) 1 . sqrtTwo' where sqrtTwo' 1 = 1 % 2 sqrtTwo' n = 1 / ( 2 + sqrtTwo' (pred n) )
Fairly simple. We directly implement the function and run it on each iteration, building a list as we go. We then filter our list so that the only entries left are the ones that have more digits in the numerator than the denominator. Lastly, we evaluate the length of that list, which gives us the answer.
Until next time!