Haskell: 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)

view raw frac.hs hosted with ❤ by GitHub

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

view raw numDemon.hs hosted with ❤ by GitHub

Those are are numerator and 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

view raw simplify.hs hosted with ❤ by GitHub

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 f' = f + (negate f')
	(+) (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)

view raw FracNum.hs hosted with ❤ by GitHub

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 Fraction is 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)

view raw FracFrac.hs hosted with ❤ by GitHub

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 and fromRational. 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 numerator and denominator functions) and turns it into a Fraction. Knowing what the numerator and 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. This kind of function is hard to read for a lot of people, but it definitely comes more naturally with Haskell practice.


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 Eq and 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'

view raw EqOrd.hs hosted with ❤ by GitHub

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 (LT, GT, or EQ) based on the relationship between two Fractions. The inequality functions are all designed around this function. The max and 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 our 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

view raw MonoidConstructor.hs hosted with ❤ by GitHub

The instance of Monoid defines a couple of functions: mempty, mappend, and mconcat. mempty is the minimal value for the Monoid. I chose 0 (which gets automatically boxed into a  Fraction). 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 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) )

view raw Euler057.hs hosted with ❤ by GitHub

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.

Pretty neat, huh? Here's the full Fraction.hs source file:



Until next time!

Ben

My first real code golf program!

I've always been interested in Code golf, which essentially boils down to creating the shortest possible program that completes some task.

I finally got around to completing one of these challenges, and though I wasn't really that close to winning, it was fun to mess around with it it was one of the shorter Haskell solutions!

So, the challenge I attempted was Reddit's Tiny Code Challenge #4, asking for the shortest program that finds the longest identical subsequence in a string.

Directly from the challenge page:

For example:
aaabbbbccc aabccdcdd -> aab, bcc
adeaabbbbccc aabccdedcdd -> aab, bcc
abcdef ghijk -> nothing
abcdef fghijk -> f

So, here was my solution in Haskell:

	import Data.List
	import System.Environment
	f=concat.r
	r []=[[]]
	r s=(scanr(:)[]s):(r$init s)
	g [a,b]=snd.maximum.map(\x->(length x,x))$intersect(f a)(f b)
	main=getArgs>>= \z-> print.g$z

view raw tc04.hs hosted with ❤ by GitHub

Let's break this down into steps, since it probably looks like a bunch of mumbo-jumbo!

	import Data.List -- gets us the function "intersect"
	import System.Environment -- gets us the function "getArgs"
	f=concat.r -- calls "r" on some input and flattens the results (concat)
	{- The function "r" takes a list of elements and produces all of it's possible sublists.
	Base case: If the input list is empty, return an empty list containing a single empty list. -}
	r []=[[]] -- base case for "r"
	r s= (scanr(:)[]s) {- recursively build substrings from the list "s"
	and push them to an empty list -}
	: -- Append the list we just built to...
	(r$init s) -- "r" called on the first n-1 elements of of the current list "s"
	g [a,b]=snd.maximum. -- finds the maximum by the length of strings
	map(\x->(length x, x)) -- groups lists into tuples of their lengths and the list
	$intersect(f a)(f b) -- The intersection* of "f" called on a, and "f" called on b
	main= getArgs >>= -- get the command line arguments as a list ["firstString", "secondString"]
	\z-> print.g$z -- bind the argument list (z) to print "g" called on z

view raw tc04Comments.hs hosted with ❤ by GitHub

And there you have it! 193 characters of Haskell code got us a pretty cool program.

Here's a little bit of output: 

>tc04.exe "aaabbbbccc" "aabccdcdd"

>"bcc"

>tc04.exe "abcdef" "ghijk"

>tc04.exe "abcdef" "fghijk"

>"f"

>tc04.exe "fhqwhgads" "where are all the dragons?"

>"wh"

Cool! :)

-Ben