Thursday, January 2, 2014

The Way You Think Puts The Fun in Functional

It's easy for programmers familiar with the regular, procedural, way of coding to dismiss functional programming. Functional programming requires a different way of thinking, and as humans we come pre-programmed with the idea that different = bad.

I don't write this in order to convince you on an objective basis, but I do want to share that for me, thinking functionally is just good fun. One of the great shames of procedural programming is that it requires you to emulate the computer in your head, which seems pretty wasteful.

Here are a couple of small examples that might tickle your fancy.

String replication

This is one of the oldest problems in data processing, ever since we padded fields with zeroes or used multiple underscores to draw lines on a report. Given a string, write code to replicate it several times. Turn "A" into "AAA", for instance. 

Here's how you probably think about this problem by default:

If you were asked to write some Python code, you might scribble out something like this:
res = ""
for i in range(0,3):
  res = res + "A"

However, now you're thinking like a computer would. Get a thing, add another thing, and so on. You're thinking about the process, not the data. Consider it another way, from the point of view of the data itself.

The string "AAA" is actually a snippet from the string of infinite "A"s, stretching on into perpetuity. So, instead all we want is the the beginning of that "ideal" sequence:

In Clojure, a functional language, you write that as something like:

(apply str (take 3 (repeat "A")))

(The apply str turns a list of "A"s into the string we want. Clojure does something called lazy evaluation, which means we don't need to bend the rules of physics to recover the infinite list of "A"s).

Now, I'm not saying it's any easier or better to understand, just a different way of thinking about things. Let's try another example.


Consider rotating a carousel of list items. Again, a common enough problem: they might be images on the front page of your web site, for instance. Here's how you likely think about this by default:

If you've some familiarity with data structures, this looks like a first-in-first-out queue to you, where you're removing the head item and stuffing it back on the tail each time. In Python, this operation looks a bit like repeating a single rotate operation for as many rotations as you want, twice in this case:

mylist = mylist[1:] + [mylist[0]]

Here's another way to think of it—any rotation of the list is actually a window onto a repeating sequence of the list itself.

So, in this case to rotate twice, we just move the "view" along twice over the original sequence. With a little thought, it looks like this in Clojure:

(take 5 (drop 2 (concat mylist mylist))

Fun, huh?

The trick is this: instead of worrying how the computer will do the operation, we concentrate on the shape of the data itself, and let the computer figure out how to do things efficiently.

It's amusing and brain stretching to think in this way, and even if you don't end up programming in a functional language, it will help you think data-first in the language you do use. It is, for example, quite possible to write many expressions in a functional way in Python.

It's also, for the record, possible to write terrible Clojure and try and solve problems the procedural way!

If you enjoyed this, I suggest tackling some of the problems over at 4Clojure.