Functional Programming 101 - With Clojure
Jan 26, 2014
Help Hercules defeat the Hydra. With functional programming.
Here goes a simple yet interesting programming problem originally proposed by Mattox Beckman. After seeing Tejas Dinkar’s take on this problem using Haskell, I decided to give it a go with Clojure.
You are Hercules, about to fight the dreaded Hydra. The Hydra has 9 heads. When a head is chopped off, it spawns 8 more heads. When one of these 8 heads is cut off, each one spawns out 7 more heads. Chopping one of these spawns 6 more heads, and so on until the weakest head of the hydra will not spawn out any more heads.
Our job is to figure out how many chops Hercules needs to make in order to kill all heads of the Hydra. And no, it’s not n!.
We can start by defining a function that returns a
To make it easy to compare both solutions, the data structure I’m using here is the same one used by Dinkar: a list. In this list, each number represents a living head and its level of strength.
Now, according to the problem description, when Hercules chops off a level 3 head, the Hydra grows two level 2 heads.
Here’s one possible implementation for such a function.
This code should make sense even if you are not familiar with Clojure.
What happens if Hercules tries to cut off the head of a headless Hydra?
Most functional programming languages I know are laid on top of a strong principle called the closure property.
In general, an operation for combining data objects satisfies the closure property if the results of combining things with that operation can themselves be combined using the same operation. Closure is the key to power in any means of combination because it permits us to create hierarchical structures – structures made up of parts, which themselves are made up of parts, and so on.
– Gerald Jay Sussman, Hal Abelson
To illustrate this concept with code, let’s consider Clojure’s
cons follows the closure principle. But what about our
function? Does the principle hold?
Apparently not. To fix that, we need to make sure
dec is not called with
nil, since it’s not possible to decrement a null value.
What about now?
Killing The Hydra
In order for Hecules to kill the Hydra, he needs to repeatedly chop off Hydra’s heads while it still has them.
(iterate f x) function returns a lazy (infinite) sequence of
(f (f x)), etc, given that
f is a function free of side-effects.
chop-head respects the closure principle by always returning a list,
we can use it in
iterate until we get an empty list, which means the Hydra
Let’s test it on a 3-headed baby Hydra.
How many chops are needed in order to kill the original 9-headed Hydra?
Another interesting question: what is the maximum number of heads Hercules fought at once?