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:

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:

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:

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:

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?

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.

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!

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:

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

Looks neat! A nice generalization is to make Fraction polymorphic. This leads to Data.Ratio (the native rational / fractions library of haskell).

ReplyDeleteE.g. Then you can define rationals over a finite field.