Graph Theory and the Handshake Problem

The Handshake Problem

The Handshake Problem is something of a classic in mathematics. I first heard about it in an algebra course I took in high school, and it's stuck with me through the years. The question is this:

In a room containing $n$ people, how many handshakes must take place for everyone to have shaken hands with everyone else? 

The goal of this short blog post will be to present a solution to this problem using the concept of graphs.

The Complete Graph

 

fig. I: A complete graph with 7 vertices

First, we must understand the idea of a complete graph. A complete graph is a graph such that each node is connected to every other node. A graphical example can be seen in fig. I.

We can use the model of a complete graph to reason about the problem at hand. The nodes in the graph may represent the people in the room, while the connecting edges represent the handshakes that must take place. As such, the key to solving the Handshake Problem is to count the edges in a complete graph.

But it would be silly to draw out a graph and count the edges one-by-one in order to solve this problem (and would take a very long time for large values of $n$), so we'll use math!

The Solution

 

To find the solution, we have to make a few key observations. The easiest way to start out in this case is to map out the first few complete graphs and try to find a pattern:

Let $n$ = the number of nodes, $e$ = the number of edges.

• $n = 1 \Rightarrow e = 0$
• $n = 2 \Rightarrow e = 1$
• $n = 3 \Rightarrow e = 3$
• $n = 4 \Rightarrow e = 6$

At this point, you may be noticing a pattern. As $n$ increases, we're adding $n -1$ edges. This makes sense -- each time a new node is introduced, it must connect to each node other than itself. In other words, $n-1$ connections must be made.

It follows that the number of the edges ($e$) in a complete graph with $n$ vertices can be represented by the sum $(n-1) + (n-2) + \dots + 1 + 0$, or more compactly as:
$$\sum_{i=1}^n i-1$$
You may already know from summation laws that this evaluates to $\frac{n(n-1)}{2}$. Let's prove it.

The Proof

Theorem: $\forall n \in \mathbb{N} : \sum_{i=1}^{n} i-1 = \frac{n(n-1)}{2}$

Proof:  Base case: Let $n = 1$. Then, $\frac{1(1-1)}{2} = \sum_{i=1}^1 i-1 = 0$.
Inductive case: Let $n \in \mathbb{N}$. We need to prove that $\frac{n(n-1)}{2} + n = \frac{n(n+1)}{2}$.
$$\begin{array} {lcl}
   \frac{n(n-1)}{2} + n & = & \frac{n(n-1)+2n}{2} \\
   & = & \frac{n^2 - n + 2n}{2} \\
   & = &  \frac{n^2 + n}{2} \\
   & = & \frac{n(n+1)}{2}■\end{array}$$
We can now use the theorem knowing it's correct, and, in fact, provide a solution to the original problem. The answer to the Handshake Problem involving $n$ people in a room is simply $\frac{n(n-1)}{2}$. So, the next time someone asks you how many handshakes would have to take place in order for everyone in a room with 1029 people to shake each other's hands, you can proudly answer "528906 handshakes!"

Until next time,

Ben

Comonadic Trees

We've seen in the previous post what monads are and how they work. We saw a few monad instances of some common Haskell structures and toyed around with them a little bit. Towards the end of the post, I asked about making a Monad instance for a generalized tree data type. My guess is that it was relatively difficult. But why?

Well, one thing that I didn't touch on in my last post was that the monadic >>= operation can also be represented as (join . fmap f), that is, a >>= f = join \$ fmap f a, as long as a has a Functor instance.

join is a generalized function of the following type:

 $$ join :: (Monad ~m) \Rightarrow m ~(m ~a) \rightarrow m ~a $$

Basically, this function takes a nested monad and "joins" it with the top level in order to get a regular m a out of it. Since you bind to functions that take as and produce m as, fmap f actually makes m (m a)s and join is just the tool to fix up the >>= function to produce what we want.

Keep in mind that join is not a part of the Monad typeclass, and therefore the above definition for >>= will not work. However, if we are able to make a specific join function (named something else, since join is taken!) for whatever type we are making a Monad instance for, we can certainly use the above definition.

I don't want to spend too much time on this, but I would like to direct the reader to the Monad instance for [] that I mentioned in the last post -- can you see any similarities between this and the way I structured >>= above?

Now back to the Tree type. Can you devise some way to join Trees? That is, can you think of a way to flatten a Tree of Tree as into a Tree a?

This actually turns out to be quite difficult, and up to interpretation as to how you want to do it. It's not as straightforward as moving Maybe (Maybe a)s into Maybe as or [[a]]s into [a]s. Maybe if we put a Monoid restriction on our a type, as such...

$$ instance ~(Monoid ~a) \Rightarrow Monad ~(Tree ~a) ~where ~\dots $$

...we could use mappend in some way in order to concatenate all of the nested elements using some joining function. While this is a valid way to define a Tree Monad, it seems a little bit "unnatural." I won't delve too deeply into that, though, because that's not the point of this post. Let's instead take a look at a structure related to monads that may make more sense for our generalized Tree type.

What is a comonad?

Recall the type signature of >>= for Monads:
$$ (>>=) :: (Monad ~m)  \Rightarrow m ~a \rightarrow ~(a \rightarrow m ~b) \rightarrow m ~b $$
That is, we're taking an m a and converting it to an m b by means of some function that operates on the contained type. In other words, we're producing a new value using elements contained inside the Monad. Comonads have a similar function:
$$ (=>>) :: (Comonad ~w) \Rightarrow w ~a \rightarrow (w ~a \rightarrow ~b) \rightarrow w ~b $$
The difference here is that the function that we use to produce a new value operates on the whole -- we're not operating on the elements contained inside the Comonad, but the Comonad itself, to produce a new value.

We also have a function similar to the Monadic return:
$$ coreturn :: (Comonad ~w) \Rightarrow w ~a \rightarrow a $$
Whereas return puts a value into a Monadic context, coreturn extracts a value from a Comonadic context.

I mentioned the Monadic join function above because I would also like to mention that there is a similar operation for Comonads:
$$ cojoin :: (Comonad ~w) \Rightarrow w ~a \rightarrow w ~(w ~a) $$
Instead of "removing a layer," we're "adding" a layer. And, as it turns out, just as a >>= f can be represented as join \$ fmap f a, =>> can be represented as:
$$ a ~=>> ~f = fmap ~f ~\$ ~cojoin ~a $$

The full Comonad typeclass (as I like to define it) is as follows:

$$ class ~(Functor ~w) \Rightarrow Comonad ~w ~a ~where \\
\hspace{22pt}coreturn :: (Comonad ~w) \Rightarrow w ~a \rightarrow a \\
\hspace{38pt}cojoin :: (Comonad ~w) \Rightarrow w ~a \rightarrow w ~(w ~a) \\
a ~=>> ~f = fmap ~f ~\$ ~cojoin ~a $$

By now, it should at least be clear that Monads and Comonads are related -- it shouldn't be hard to see why they are so similar in name!

Note: There is a package called Control.Comonad on Hackage. It uses different names for the Comonad operations, but they do the same things. It's a good package, but I wanted to show how Comonads are built and use the operation names I used to make things clearer.

What can I do with Comonads?

As it turns out, the Tree a structure that I've been mentioning fits into the Comonadic context quite well, and provides a simple example as to how Comonads work.

We'll start with the implementation of the Comonad typeclass mentioned above:

Then we'll go ahead and make a Functor instance of our Tree a data type:


From here, we're able to make a Comonadic Tree like so:


The only real point of confusion here is in the cojoin function for Nodes. But, all we are doing is wrapping the entire node in a new node, and then mapping cojoin over every child node of the current node to produce its children. In other words, we're turning a Node a into a Node (Node a), which is exactly what we want to do.

So what can we do with a comonadic tree? Let's tackle a simple problem. Say we're hanging out in California, and we want to get to the East coast as quickly as possible. We don't really care where on the East coast we end up -- we just want to get there. We can map out the different paths that we can take, along with the time it takes to get to each one. In other words, we're going to model spots on the map as Nodes on a Tree and give them a weight corresponding to the time it takes to get there. We can model this situation with a Tree as follows:


The number of each Node marks its distance from the previous Node. The root Node of the Tree is the starting point, so it is 0 distance away from itself.

What we want to do to find the shortest path through the country is essentially, as follows. First, we're going to need to check the deepest nodes, and find their minimum distance children. We will add the distance of the Node closest to the one we're examining to its own distance, to find the shortest way to get from the node we're examining to the destination. Once all of that has been done, we'll need to traverse up the tree, repeating this as we go. By the end of the algorithm, the root Node will be marked with the shortest distance to the destination.

Now, that may sound somewhat iterative in nature, but we're going to morph this into a comonadic operation. First, let's take a look at a function we can use to find the minimum distance to the next level of our tree:


This is relatively simple, and does precisely what was mentioned above: adds the minimum value contained in the connected Nodes to the parent Node. Next, take a look at the type signature. We can see that this function produces a new number from a tree full of numbers. This coincides precisely with the function type we need to use with =>>, so we'll be able to use it to get exactly what we want.

The rest is very simple:



This produces a tree full of the minimum distances from each node to the East coast. Pulling the actual value out is as easy as calling coreturn on the resultant tree.

Thanks for reading!

Ben

For further reading on Comonads, I recommend the article Evaluating Cellular Automata is Comonadic.

Introductory Monads

What is a Monad?

If you've used Haskell before, chances are that you've heard the term "monad" a good bit. But, you might not know what they are, or what they are really used for. It is my goal in this blog post to shed some light on what monads are, introduce and define few simple ones, and touch on their usefulness.

I will assume basic familiarity with Haskell syntax in this blog post. A working knowledge of monoids and functors will also be beneficial, although not strictly necessary.

Without further ado, let's go ahead and look at the Monad typeclass:


We can see a Monad has two operations, return and >>= (this is commonly pronounced "bind"). You may suspect that you know what return does from other programming languages, but be warned: Haskell's return is very different! Haskell's return only operates on Monads, and essentially acts as a "wrapping" function. That is, if you call return on a value, it will turn it into a monadic value of that type. We will look at an example of this shortly. The second operation, >>=, takes two arguments: an a wrapped in a Monad m (I will refer to this as m a from now on), and a function that converts an a to b wrapped in the same type of Monad, m. It produces a value of type b, wrapped in a Monad m (I will call this m b from now on). This may sound complicated, but I'll do my best to explain it after showing the most basic Monad type, namely, the Identity Monad:



Also defined in Control.Monad.Identity

The Identity data declaration defines only one type: Identity a. Basically, this is just a wrapper for a value, and nothing more. return is simply defined as Identity. We can, for example, call return 3 and get an Identity 3. Turning values into Identitys is as simple as that. The bind function may look a little bit more obscure, though. Let's look closely: We first use pattern matching to be able to operate on the type that the Identity Monad wraps (Identity a), bind it (>>=) to a function (f). Since f converts normal values into monadic ones (look at the type declaration), we can simply apply f to a, and we've produced a new Identity. I've provided a couple of examples of how this works. addThree adds 3 to an Identity Int (m1) and getLength turns an Identity [a]  (m2) into an Identity Int. Both of the bind examples produce the value Identity 6. Can you see why?

I want to take a little sidebar here and try to explain how I understand Monads before moving on. Basically the real tough part of understanding Monads is just understanding >>=. A little bit of dissection can explain a lot, but it took me months to really grasp the concept. On the surface, you're morphing an m a into an m b. At first, I thought that the m's in the type signature were allowed to different types of Monads. For instance, I thought that Monads made it possible to bind Identity Ints to functions that produced [String]s (we'll look at the list Monad in a minute). This is wrong, and for good reason! It was incredibly confusing to think about a function that could generalize to this degree and it is, to my knowledge, not possible to do so. The Monad (wrapper) type is retained, but the wrapped type can be changed by means of the function you bind to.

The second thing that I want to stress is what >>= really does. What we're doing with the >>= function is turning an m a into an m b, but it's not so direct as you might want to think. The function argument in >>=  ( (a -> m b) ) was really confusing to me to begin with, so I'm going to try to explain it. The function you're binding your m a to must take an a and return an m b. This means that you're acting on the wrapped part of the Monad in order to produce an entirely new Monad. It took me a while to realize what exactly was happening, that I wasn't supposed to be directly converting m a to m b by means of my argument function (that's actually what >>= is for). Just remember that the function you bind to should operate on an a to produce an m b.

With that knowledge, let's take a look at some more examples of Monads:

More Monads

If you're a Haskell user, you're likely already familiar with the Maybe data type:

Defined in the Prelude

The Maybe Monad is hardly an extension of the aforementioned Identity Monad. All we are really adding is the functionality to fail -- that is, to produce a Nothing value if necessary. In fact, the Just a type is exactly the same as Identity a, except that a Nothing value anywhere in the computation will produce a Nothing as a result. Next, we'll look at the Monad instance for lists:



Defined in the Prelude

The list Monad is a little more complicated, but it's really nothing too new. For return, we just have to wrap our value inside a list. Now, let's look at >>=. concatMap actually is the >>= instance for lists. Why? Well, concatMap is, simply, (concat . map). We know that map takes a list of as and maps a function over them, and concat is a function that flattens lists, that is, turns [[a]]s into [a]s. When we compose these two functions (or use concatMap), we're making a function that must produce [[a]]s out of [a]s, and then flatten them back to [a]s. That is exactly how >>=  works for lists! Now, let's take a look at a slightly more complicated Monad:



Also defined in Control.Monad.Instances

This one requires some explanation, because it's a bit of a leap from the last three, since we're defining a Monad instance for functions. I have added a couple of comments in the above code in order to further explain how everything is working in the (->) r Monad.

Well, first things's first. We define return as const, which takes some arbitrary argument and produces a function that produces a constant value (what we pass in to return). This is exactly what we want; a minimal context for functions.

(>>=) is a bit more complex. First, let's take a look at the type signature, specific to this Monad. We're binding a function (r -> a) to a function (a -> (r -> b)) to produce a function of type (r -> b). So in the declaration of the function, f is of type (r -> a) and g is of type (a -> (r -> b)). I've conveniently named the argument our function is going to take r, for clarity. This is what the user will pass into the function that (>>=) produces.

f takes an r, so we apply the value from the lambda into it to produce an a. We then use that a to produce an (r -> b), using g. This produces our function, but it needs to be fed some value, so we finally apply it to r in order to complete everything. If any of this sounds confusing, try to work through it on paper and read the comments in my code -- after a bit of staring, it should start to make sense.

I've also implemented the mean function here, using the (->) r Monad with and without do-notation. I think it's a pretty elegant way to express it.

We've only seen the tip of the iceberg when it comes to Monads, but this should serve as a good basic introduction. Once you get used to seeing Monads, they become a bit less scary. The more time you spend with them, the more comfortable you'll feel with them.

Before I end this post, I want to leave a question for the reader. Given the general Tree data type represented below, can you intuitively make a Monad instance?



I'll explain why this is difficult when we talk about a similar mathematical type in the next post.

Thanks for reading,

Ben

For more introductory monad material, I suggest the following resources:

• Learn You a Haskell For Great Good! A Fistful of Monads
• A Neighborhood of Infinity - You Could Have Invented Monads
• Brian Beckman - Don't Fear the Monad

Uncountable Infinity and The Diagonalization Method

Introduction

I took a class on Discrete Mathematics this past semester, and one of the topics we covered very briefly was the concept of countable and uncountable infinity. I didn't end up getting a great grasp on it, however, and the topic I'm writing about today didn't make a lick of sense to me at the time. It was never covered on exams, so I never had to revisit the idea. But, I've been reading through Douglas R. Hofstadter's Gödel, Escher, Bach, and it just so happens that the topic is covered in the book. As it turns out, it's not actually too difficult a thing to understand, so I'm hoping to relay the ideas in this blog post. If you've heard about the concept of multiple infinities but not understood it, hopefully this will shed some light! If you haven't yet heard about the concept of multiple infinities, enjoy the read!

Anyway, on with the show...

Natural Numbers Form an Infinite Set

It is a widely known fact (axiom of ZFC Set Theory) that the set of natural numbers (all non-negative integers) extends on to infinity. That is to say, there is no "largest" natural number. We can order the set of natural numbers in this way:

$$
\begin{matrix}
N_0 & = & 0 \cr
N_1 & = & 1 \cr
N_2 & = & 2 \cr
N_3 & = & 3 \cr
N_4 & = & 4 \cr
N_5 & = & 5 \cr
\cdots
\end{matrix}
$$
This ordering comes very naturally to us. The nth term of the set of natural numbers will be, simply, n. Because of this fact, we can tell that this set of natural numbers contains all of them -- if you give me any natural number, it will correspond to the nth number in the set.

There is a similar way of ordering the integers (including negatives) in this fashion. It may not be heavily intuitive at first, because we have to extend in two directions rather than one. But, it is apparent that this ordering of integers will allow us to find the location of any integer in it:

$$ \begin{matrix}
Z_0 & = & 0 \cr
Z_1 & = & 1 \cr
Z_2 & = & -1 \cr
Z_3 & = & 2 \cr
Z_4 & = & -2 \cr
Z_5 & = & 3 \cr
\cdots
\end{matrix}
$$
Any integer, positive or negative, is contained in this infinite set. An infinite set that can be ordered in a way such as this is said to be countably infinite.

What About Real Numbers?

For the purposes of this post, we're going to focus on the real numbers between 0 and 1. We can represent them in the following way:

$$
\begin{matrix}
R_0 & = & 0 . & a_0 & a_1 & a_2 & a_3 & a_4 & \cdots \cr
R_1 & = & 0 . & b_0 & b_1 & b_2 & b_3 & b_4 & \cdots \cr
R_2 & = & 0 . & c_0 & c_1 & c_2 & c_3 & c_4 & \cdots \cr
R_3 & = & 0 . & d_0 & d_1 & d_2 & d_3 & d_4 & \cdots \cr
\cdots
\end{matrix}
$$
We can see that this set goes on forever, that is, extends infinitely, just as the set of integers and naturals does. However, the set of real numbers is "built" in a different way. Both of these facts are important in what we will observe next.

Cantor's Diagonalization Method

I claim now that I can produce a number that the above set does not contain. To do this, I will be using Georg Cantor's famous Diagonalization Method. Here's how it works.

First, I will grab the $n$th term of each $n$th element in our set of real numbers to compose a new number, like so:

$$
\begin{matrix}
R_0 & = & 0 . & \color{red}{a_0} & a_1 & a_2 & a_3 & a_4 & \cdots \cr
R_1 & = & 0 . & b_0 & \color{red}{b_1} & b_2 & b_3 & b_4 &\cdots \cr
R_2 & = & 0 . & c_0 & c_1 & \color{red}{c_2} & c_3 & c_4 & \cdots \cr
R_3 & = & 0 . & d_0 & d_1 & d_2 & \color{red}{d_3} & d_4 & \cdots \cr
\cdots &&& &&&& \color{red}{\ddots}
\end{matrix}
$$
So my new number becomes:

$$
\begin{matrix}
0 . & a_0 & b_1 & c_2 & d_3 & \cdots
\end{matrix}
$$
Now I'm going to perform some transformation on each digit of this number to produce a new digit. A simple way (the simplest way?) to do this would just be to add 1 to each digit. This will produce a new number as follows:

$$
\begin{matrix}
M_0 & = & 0 . & a_0 + 1 & b_1 + 1 & c_2 + 1 & d_3 + 1 & \cdots
\end{matrix}
$$
We can see $M_0$ cannot be the same as $R_0$ because its first term differs. Same goes for $R_1$ with its second digit, and so on, ad infinitum. Therefore, each element of set of real numbers between 0 and 1 is going to differ from $M_0$ by at least one digit. We can conclude from this observation that our (infinite!) set of real numbers excludes $M_0$. That is to say, our set of real numbers between 0 and 1 isn't actually complete, and cannot actually be complete.

That last part, "cannot be complete," may sound confusing, because, why can't we just add $M_0$ to the set, and call it complete?

Well, let's do it! We'll tack on $M_0$ to the set to produce something like this:

$$
\begin{matrix}
M_0 & = & 0 . & a_0 & b_1 & c_2 & d_3 & e_4 & \cdots \cr
R_0 & = & 0 . & a_0 & a_1 & a_2 & a_3 & a_4 & \cdots \cr
R_1 & = & 0 . & b_0 & b_1 & b_2 & b_3 & b_4 & \cdots \cr
R_2 & = & 0 . & c_0 & c_1 & c_2 & c_3 & c_4 & \cdots \cr
R_3 & = & 0 . & d_0 & d_1 & d_2 & d_3 & d_4 & \cdots \cr
\cdots \cr\
\end{matrix}
$$
You might foresee what's going to happen next. We can perform diagonalization again:

$$
\begin{matrix}
M_0 & = & 0 . & \color{red}{a_0} & b_1 & c_2 & d_3 & e_4 & f_5 & \cdots \cr
R_0 & = & 0 . & a_0 & \color{red}{a_1} & a_2 & a_3 & a_4 & a_5 & \cdots \cr
R_1 & = & 0 . & b_0 & b_1 & \color{red}{b_2} & b_3 & b_4 & b_5 & \cdots \cr
R_2 & = & 0 . & c_0 & c_1 & c_2 & \color{red}{c_3} & c_4 & c_5 & \cdots \cr
R_3 & = & 0 . & d_0 & d_1 & d_2 & d_3 & \color{red}{d_4} & d_5 & \cdots \cr
\cdots & & & &&&&& \color{red}{\ddots} \cr
\end{matrix}
$$
...to produce a new number...

$$ \begin{matrix} 0. & a_0 & a_1 & b_2 & c_3 & d_4 & \cdots \end{matrix} $$
We perform some transformation on its elements (let's add one, again) in order to get a new number, say $M_1$.

$$ \begin{matrix} M_1 & = & 0. & a_0 + 1 & a_1 + 1 & b_2 + 1 & c_3 + 1& d_4 + 1 & \cdots \end{matrix}$$
However, note that $M_1$ must differ from $M_0$ now, as well as every other number in the set, by at least one digit. As such, $M_1$ must not yet exist in the set. We can add $M_1$ to the set, and repeat this process as many times as we want, but we'll always be able to produce a number outside of the set! We call a set with this fascinating property uncountably infinite.

What does this mean? We can see that the set of integers is countably infinite, while the set of real numbers between 0 and 1 is uncountably infinite. We have successfully proven in this blog post that there are actually more numbers between 0 and 1 than there are integers!

Cantor's Diagonalization Method has been used to prove several difficult problems in Mathematics, including the Church-Turing Theorem and Gödel's Incompleteness Theorems. All three of these theorems have had major effects on the nature of Mathematics, so you can see that Cantor's Diagonalization Method can be quite useful!

If you have any questions, or if anything was unclear, please leave a comment!

Until next time,

Ben

Graphs and Topological Sorting in the Functional Paradigm

What is a Graph?

From Wikipedia: 

In mathematics, a graph is a representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges.

Simply put, a graph is just a bunch of points with links between them. A road map is a simple example: roads  being edges, and intersections being vertices.  In fact, Google maps uses graphs for just this purpose! Graphs are widely used in a wide variety of places. Facebook uses graphs to model your friend connections and likes. In fact, the entire internet is just a giant graph; websites act as vertices, with hyperlinks as edges. Graphs are highly useful structures, as they can be used to model many different types of situations, and as such, they will be the focus of this blog post. I am going to discuss one way to represent a graph in the Haskell programming language, and how to functionally solve a common problem using graphs.

Graphs are often represented visually like this:

Graph representing abstract data

This graph links the first six letters of the alphabet in an arbitrary way. This data doesn't really mean anything, but it will serve as a simple foray into the world of graphs, and provides an initial graph to work towards representing in Haskell.

Let's get right to it; here's the data structure we'll be using, along with some convenience methods:


First we define the actual Graph a data type: It's simply a set vertices and edges in the form of 2-tuples (The tuple (a, b) connects vertex a to vertex b), which fits our definition. I've also defined the removeEdge method, which does just what you'd expect. The outbound and inbound methods find the outbound and inbound connections to any point in the graph, respectively. They make use of the polymorphic connections method in order to get this done in a small amount of code. Finally, the Graph module exports the relevant functions at the top of the file.

Now that we've got our framework in order, we can go ahead and build the graph we mentioned above:


We import the Graph module and define a simple Letter data type, then build our Graph from it. The set of vertices are the letters A, B, C, D, E, and F, and the edges are modeled as above.

Now that we know how to build graphs, we can start modeling more important information with them.

Modeling Actual Scenarios using Graphs

Suppose some of the characters from NBC's Parks and Recreation have just finished competing in a dance competition, and we know the following about their rankings:

Leslie beat April.
April beat Ann.
Ron beat April.
Ron beat Ann.
April beat Andy.
Leslie beat Ron.
Andy beat Jerry.
Ron beat Andy.
Ann beat Jerry.
Leslie beat Andy.
Ann beat Andy.

This is a little hard to understand, so why don't we model it as a graph to make it a little more readable? Each person can be represented as a vertex, with outgoing edges representing connections to the people they beat.

A graph of dance competition results

It would be nice to be able to be able to read scenarios like this from a text file containing the important data and parse it into a graph. Let's go ahead and set up a function to do this for us, so we don't have to hard-code each and every graph that we want to use:

Here's our data file, with a list of space-separated connections, one on each line:




And our parsing function:


The graphFromFile function takes a String and returns an IO (Graph String).  The function reads a file, parses it into two important pieces: verts (the set of all unique strings in the file, or, our vertices) and conns (the set of connections between strings in the file). It then builds a Graph from this data, wraps it in the IO monad with return, and gives it back.

Now you might have been wondering from the beginning of this section what the ranking from the dance competition was (maybe you even figured it out on your own!). How do we do this programmatically, using our graph?

Enter Topological Sort

Again, from Wikipedia:

In computer science, a topological sort of a directed graph is a linear ordering of its vertices such that, for every edge uv, u comes before v in the ordering.

In our case, this just means that each person must come before all of the people that he or she beat in the competition, in the ordering.

The basic procedure for topological sort is as follows:

L = {} --sorted list
S = Set of vertices with no incoming connections
while S is not empty:
    for each vertex v in S with no incoming connections:
        push v to L
        for each edge e from v to u:
            remove e from graph
            if u has no more incoming connections:
                push u to S

if edges still exist in the graph:
    error: there is at least one cycle in the graph

else return L

If you do not understand this, I urge you to work through topologically sorting a graph on paper first; it's not too tough to understand once you've done it on paper, but can get a little confusing in psuedocode.

The problem with this algorithm is that you see a ton of loops -- control structures that we do not have in Haskell. Therefore, we must rely on recursion, folds, and maps to achieve what we want to do. Here's how it looks:



Our tsort function first finds the elements in the graph with no incoming edges using the function noInbound.  We pass this into a sub-routine tsort' that takes a sorted list l, a list of vertices with no incoming connections (n:s), and a graph g.

We operate on the first element of the set of vertices with no incoming connections n, finding outEdges (the outgoing edges from n), and outNodes (the nodes that n points to). We build a new graph g' with the outEdges removed, and find the nodes in g' with no inbound connections, and add them to s.

We then recursively call tsort' with these new parameters (and prepend our current n to the sorted list), until there are no more nodes to check. At this point, if the edge list in the graph is empty, all is well and we return the list of sorted elements. Otherwise, an error is thrown stating that there is at least one cycle in the graph.

Now that we've got that, we're ready to find out how everyone ranked in the dance competition!



This produces the output:
["Leslie", "Ron", "April", "Ann", "Andy", "Jerry"]

(Of course Jerry lost.)

Conclusion

As you can see, Graphs are very useful data structures. They can be used to model a huge variety of things (see how many more you can come up with, they're everywhere!). Topological sort in particular is a pretty remarkable algorithm, and can be applied in many different situations from the one above. For example, finding paths through college courses with prerequisites. It's even used in UNIX systems to schedule processes according to their dependencies.

Hope you enjoyed the post! Until next time,

Ben

"Memorizing" the Unit Circle

I, like many others I'm sure, was told that I needed to memorize the unit circle while studying Pre-calculus in High School. This looks like a very daunting task at first glance, and it caused me a lot of frustration the first time I learned it.

I was taught to memorize them straight. I don't know why, because there's a much, much, better way to go about it. I'm going to start with the full unit circle and widdle down "memorization" to the bare minimum. Once you can start to see the reality of what the Unit Circle is, it becomes way easier to interpret.

The Unit Circle

First off, the unit circle is just a circle of radius 1. Knowing this, we can determine that its circumference is $c = 2\pi r = 2\pi 1 = 2\pi$ radians. Points on the unit circle are easy to find knowing that the circumference is just $2\pi$. We just have to figure out what fraction of $2\pi$ our target angle is, and locate that section on the circle.

So what's our goal? We need to be able to extract the trig functions from the unit circle:

$$sin\theta,   cos\theta,   tan\theta,   csc\theta,   sec\theta,   tan\theta$$

at each interval of $\frac{\pi}{6}$, or $30˚$, and each interval of $\frac{\pi}{4}$, or $45˚$.

To do this, we need to know a little bit about the way that the coordinate system on the unit circle works. At any given point on the unit circle, we can make a triangle starting from the center of the circle to said point that rests on the x axis.  The hypotenuse of this triangle will always be $1$, simply by the definition of the unit circle. We know that $sin = \frac{opposite}{hypotenuse}$ and $cos = \frac{adjacent}{hypotenuse}$ for any angle on a triangle. We have noted that our $hypotenuse$ will always be $1$, so the $sin$ of any angle on the unit circle will simply be the $\frac{opposite}{1}$, or the length of the opposite side, otherwise known as our $y$ coordinate. Similarly, $cos = \frac{adjacent}{1}$, or the length of the adjacent side: our $x$ coordinate.

Knowing this, the cases of $0\pi,   \frac{\pi}{2},   \pi, $ and $\frac{3\pi}{2}$ become trivial -- All we need to do is point out which coordinate is $0$, and which one is $1$, and we have both $cos$ and $sin$.

So, what about the rest of them? These are the only three fractions that I like to keep in mind when dealing with the unit circle angles. Commit these to memory: 

$$\frac{1}{2},   \frac{\sqrt2}{2},   \frac{\sqrt3}{2}$$

These (and their negations) will be our $cos$ and $sin$ values for any "special" point on the unit circle, and as such, they are all we need to remember (the rest of the trig functions can be derived from these values).

Let's first just deal with the first quadrant angles, $\frac{\pi}{6},   \frac{\pi}{4},   \frac{\pi}{3}$. The first thing that I want to do is order the fractions above from smallest to largest. I've actually written them in the correct order; so I won't bother writing them out again. Now, let's think about this for a second. In the first quadrant, out of our three points, where is $sin$ (our $y$ coordinate) the smallest? We start at $0$, and our $y$ value gets closer and closer to $1$ as the angle increases. This means that the smallest angle of our three ($\frac{\pi}{6}$) gets the smallest $sin$ value. Following this convention, we can say that our middle angle ($\frac{\pi}{4}$) gets the middle $sin$ value ($\frac{\sqrt2}{2}$), and our largest angle ($\frac{\pi}{3}$) gets the largest $sin$ value ($\frac{\sqrt3}{2}$). 

But wait! Didn't we say that our $cos$ value is simply the $y$ coordinate? Yes, and as such, this idea can be applied to the $cos$ values as well. $cos$ ($x$) is decreasing as we move from $0$ to $2\pi$ on our unit circle, though, so as angles increase, $cos$ decreases. Apply the logic from before, and we have:

 $$cos \frac{\pi}{6} = \frac{\sqrt3}{2},   cos \frac{\pi}{4} = \frac{\sqrt2}{2},   cos \frac{\pi}{3} = \frac{1}{2}$$

Knowing this, you know the rest of the values on the unit circle. Why? Because we can see where the $x$ or $y$ coordinates are negative, and it is obvious which one is larger than the other at any point. For example, take $\frac{5\pi}{6}$. Here, we can see that the $x$ coordinate is negative, but the $y$ coordinate is positive. So, we have a positive $sin$ and a negative $cos$. The length of the $y$ side is clearly shorter than the length of the $x$ side, so we can see that $sin \frac{5\pi}{6} = \frac{1}{2}$ and $cos \frac{5\pi}{6} = -\frac{\sqrt3}{2}$. Note: At intervals of $\frac{\pi}{4}$, we will always have the same ratio for both $sin$ and $cos$: $\frac{sqrt2}{2}$. It's just a matter of getting the signs correct!

So, what about the rest of the trig functions? Well, let's start with $tan$. We know that $tan\theta = \frac{opposite}{adjacent}$, right? Well, our $adjacent$ side on the unit circle is just $cos$. Our $opposite$ side is just $sin$. Therefore, on the unit circle, $tan\theta = \frac{sin\theta}{cos\theta}$. Since we can get $sin$ and $cos$, we can just divide them out and get our $tan$ value. Simple.

$sec\theta$,   $csc\theta$,  and $cot\theta$ then become trivial. All we need to do is take the reciprocals of their counterparts ($cos\theta$, $sec\theta$, and $tan\theta$ respectively). $\frac{1}{2}$ becomes $2$, $\frac{\sqrt2}{2}$ becomes $\sqrt2$, and so on.

And that's all of the trig functions for the "essential points" on the unit circle. All that is truly necessary is the recalling of three simple fractions and a few key concepts, and the whole thing becomes easy.

Hope this helps!

-Ben

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:



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