Haskell and the Towers of Hanoi

I’ve been interested in Haskell for a couple of months now, but teaching at Portland Code School has been keeping me busy enough that I haven’t had the time to give it more than a cursory glance. Over the week of Labor Day, we gave the students some extra time off, so I took that time as a chance to finally delve into it some more and start going through the exercises and materials from a well-reviewed course from UPenn that I found. One of the earlier exercises is to solve the Towers of Hanoi in Haskell. Before I get into my solution, though:

What is Haskell?

It’s a strongly-typed, lazy, purely functional programming language. The syntax of Haskell is like nothing I’ve ever worked with before, which is hard enough—even working with types is a big shift from JavaScript and Ruby—but the real differences come in how you put your code together, and indeed in how you think about the problems you’re solving. While this makes it an occasionally frustratingly difficult language for me to code in, it’s also why I decided to go for Haskell as my next language, rather than something like Java or C#: Haskell will require me to think about code in a very different way.

The biggest differences (that I’ve seen so far) come from Haskell being a purely functional language. What this means is that everything in Haskell comes down to functions. If you say x = 4, you are defining a function called x that returns a value of 4—variables aren’t really a thing in Haskell. In fact, data is immutable in Haskell: you can’t then go on to say that x = "cat", not just because of typing but because you’ve already given x a value; you can’t change your mind about what x is. What are you, some kind of liar? You said x was 4! Finally, functions only have return values—no side effects. That means no changing values anywhere else (not that you can change values, so no big deal there) or doing anything at all other than telling the user what answer the function spits out. This leads to a whole different way of thinking about code. As Learn You a Haskell likes to say: “Object oriented languages talk about what a thing does. Functional languages talk about what a thing is.”

The Towers of Hanoi

The Towers of Hanoi is a game (which itself features in a number of BioWare games) in which you have three pillars, one of which has a stack of increasingly smaller rings on it. The goal of the game is to move the rings from one pillar to another pillar. When doing so, you are not allowed to move more than one ring at a time, and larger rings cannot go on top of smaller rings.

Thinking about a solution, my initial instinct was to figure out some way to represent the state of the board: which rings are on which pillar? After all, you need to know if you’re moving a ring to a valid position, so you need to keep track of what’s on each pillar, right? If I were working in an object-oriented language, I would probably have started by creating objects to represent pillars, perhaps each with an array to hold the values of the rings on that pillar and a method to determine if there is a valid move available, and another method to move a ring. Something like that. But Haskell doesn’t do object oriented (not having objects), so I had to figure out a different approach. I laid out the simplest cases in Haskell:

For those who haven’t seen it, this may look fairly alien. The first three lines are type declarations: first we declare that there’s a type Peg which is a String. Fair enough. Then, type Move, which is a tuple of Pegs. Tuples are somewhat like arrays, expect they can only ever have two things in them. Tuples can take two different types of things, or two of the same thing, but once you’ve set that for a particular kind of tuple, that’s it—our tuple can only take pairs of Pegs. The third line is the type definition of our actual function. We declare a function called hanoi, and say it has the type of everything that comes after the :: operator. So this particular function takes in an Integer and three Pegs, and gives us back [Move]. This is not an array, but a list—pretty similar (to the point that I have to keep reminding myself not to call lists arrays), but apparently different in some critical ways I haven’t gotten to yet. So if we say hanoi 1 "a" "b" "c", we should get back a list of the move required to move 1 ring from "a" to "b": [("a","b")].

So, the first three lines are all setup, basically. The next two lines are the function itself. Haskell uses pattern matching in functions, which is what you’re seeing here. Line 4 says that given an initial value of 1 and three Peg names, the function will return a list containing the value of the first peg and the value of the second peg, just like we saw above. The names I’ve chosen for the pegs, incidentally, are :o for origin, x marks the (destination) spot, and t for temporary storage. Line 5 details the moves required in the somewhat more interesting case of having two rings on the pole: you move the first ring from the origin to the temporary storage, then the second ring to the destination, and the first ring from the temporary storage onto the destination. Simple. So, how does 3 work, and is there some kind of simple algorithm?

This lead to me spending some time playing with a quarter, a nickel, and a dime on a piece of paper with three boxes on it to try to come up with a different solution. I banged my head against this for an hour or two, feeling like the answer was right there, if only I could see it, before real life intruded and it was time to get back to work on curriculum for the coming week. I ignored it, but my subconscious apparently couldn’t let go of the problem, because last night as I was trying to get to sleep, I had it. In one more line of code.

The Solution

Haskell uses recursion (which is a lot of fun to Google) pretty much constantly—after all, if you can’t change values, you can’t have a counter, and if you don’t have a counter, it’s pretty hard to have a loop, so if you’ve got something you want to do repeatedly, your only real option is to set your functions up so that they call themselves until they’re done. The solution to the Towers of Hanoi does, too. This makes for a surprisingly compact solution. The idea is: We know how to move a tower comprising a single ring: we move that ring from the origin to the destination. We also know how to move a tower comprising two rings: We move the top ring to a temporary storage pillar, then move the bottom ring to the destination. Then we can put the smaller ring back on top of the bigger ring on the destination. Sweet. But things get way more complicated with more rings, so it must be much more complex, right? After all, given a number n, it takes n^2 -1 moves to get a solution!

As it turns out, knowing how to move one ring and two rings is pretty much all we need. If you want to move three rings, all you need to do is move the top two rings (which we know how to do). That leaves the bottom ring free and the top two on one pillar, so the bottom ring can move. Now you move the smaller two rings back on top of the biggest ring. Four rings? Well, now we know how to move three rings, so we do that. Next move the bottom ring, then move the three rings back. And that lets us do five, which lets us do six, and on and on.

But how do you make sure that the rings are going to the right places? This is the thing that jolted me up from almost asleep last night: it’s all in the parameters you pass to the recursing functions. When we’re moving three rings, we know that we want the whole stack to go from the origin to the destination. To do that, we have to move two rings from the origin to the temporary ring, then one ring from the origin to the destination, then from the temporary to the destination. So in the end, our program looks like this:

And that’s it! No objects, no variables representing which rings are where, nothing but a super-simple recursive function that calls itself. For hanoi 3 "a" "b" "c" we call hanoi 2 "a" "c" "b", moving two rings from "a" to "c" with our predefined line 5. Then we use line 4 to move a single ring from "a" to "b", then hanoi 2 "c" "b" "a" to move two rings from "c" to their new home on "b". It’s almost maddeningly simple. Which is exactly the kind of thing I was hoping to get out of Haskell.

Just as an exercise in fun, here’s how you might implement this in JavaScript:

Instead of Haskell’s pattern matching, we’ve got a switch statement doing basically the same thing. After that, the code is pretty much identical, except that we’re using an array of arrays as opposed to a list of tuples, and the variable names are more verbose (which somehow seems both friendlier and harder to read).

Leave a Reply

Your email address will not be published. Required fields are marked *