Why functional programming?

The canonical answer to that question is probably “Why functional programming matters“, but here’s a specific example that makes the case nicely.

Neil Mitchell is working on Supero, an optimizing compiler for Haskell which includes some ideas from supercompilation. But that’s not important right now.

What is important is the technique Mitchell uses in the blog post at the second link above. Algebra. As in junior-high-Algebra-I-algebra. The old “if a = b then you can substitute either one for the other” kind of Algebra.

Functional programming is based on defining functions.

  def square(i: Int) = i * i

In pure functional programming, where side-effects are not allowed (or at least kept securely behind bars), you can treat that definition as an equation; wherever you see square(foo) you can rewrite it as (foo * foo) and vice versa. This applies even when foo is an arbitrarily complex expression (don’t worry about operator precedence or extra parentheses right now; that’s not the point).

The point is that you can’t do that with confidence for impure (i.e., having side-effects) languages. Consider trying that replacement in something as simple as…

  n = square(++i);

…which clearly is not the same as…

  n = ++i * ++i;

…at least in most cases. Are there any special cases where it’s the same? Would the answer be different if the enclosed expression had been i++ instead?

If you even had to think about it for one millisecond (or, like me, thought “That’s ugly! I’ll think about it later!”) that’s exactly the point. In a pure language the question can’t even come up. You’re free to do the rewriting, either way, any time.

(Fair warning: You don’t need to know Haskell to read Mitchell’s post, but it helps. Even if you don’t, it’s worth the little bit of time it takes to work through his example. The cheat sheet at the bottom of this post is a quick introduction for non-Haskell-speaking readers, or non-Haskell-reading speakers.)

Mitchell takes a simple task, breaking a string into a list of words, and shows a simple and obvious function for the task. However, that simple and obvious function ends up with redundant “is it a space?” tests against some characters. Mitchell does a bit of refactoring, using simple substitute-equals-for-equals steps, to track down and eliminate the redundance, resulting in an equivalent (still simple) function that runs faster.

All of this is based on the facts that:

• more powerful functions can be composed out of simpler ones, and
• pure functions ensure that the obvious substitutions work.

For me this makes a powerful demonstration of the benefits of the functional approach, whether I’m using Haskell, Scala, or even a non-FP language such as Java. (Not only does functional programming matter, knowing why functional programming matters matters as well.)

---

Cheat sheet

For newcomers to Haskell notation, here’s a bit of explanation. Please don’t hold the length (or any shortcomings) of my explanation against Haskell. I’m assuming a reader who’s never seen Haskell before (or any similar language), and so say something about almost every token. Feel free to skip the obvious, with my apologies.

Mitchell’s analysis works on this original function…

  words :: String -> [String]
  words string = case dropWhile isSpace string of
                     [] -> []
                     s -> word : words rest
                         where (word, rest) = break isSpace s

…which breaks a string into a list of words (strings).

The special-character soup isn’t really that bad, if you use your Captain Zowie decoder ring. It helps to know three facts:

• indentation shows nested structure, instead of using curly braces,
• function application doesn’t require parentheses, and
• a Haskell String can be considered as a list of characters.

The first line…

  words :: String -> [String]

…declares the type of words as function from string to list of strings. Specifically:

• the double-colon can be read “has type”,
• the arrow indicates a function taking the type on the left, yielding the type on the right, and
• the square brackets on the right read “list of”.

The second line…

  words string = case dropWhile isSpace string of

…starts the definition of words, using a parameter named string (which we already know is of type String from the first line). The phrase…

  dropWhile isSpace string

…returns a left-trimmed version of string. It applies isSpace to successive elements of string, repeating as long as the result is true, and returns what’s left (either because there’s nothing left or because a character is found for which isSpace is false). It does so without modifying the original string, just as String#substring does in Java. That left-trimmed (sub-)string is then subjected to a case analysis, by way of pattern matching.

Remember that the result of left-trimming was produced either because there were no characters left, or because a non-space character was found. Therefore, there will be two cases to consider. The line reading…

  [] -> []

… reads “if you have an empty list (of characters) then return an empty list (of Strings)”. We (and the Haskell compiler!) can infer the parenthesized types because we know that trimming a string produces the String (list of characters) being inspected, and the type declaration on the first line says that the function produces a list of String.

The last two lines address the case in which there actually were some characters left after trimming.

  s -> word : words rest
      where (word, rest) = break isSpace s

For a non-empty string s… Wait! What’s s and how do we know it’s a non-empty string? Remember that we’re in a case (glance back at the original above to see the indentation) and we’ve already eliminated the possibility that the trimmed string we’re examining is empty. So the value in hand must be non-empty. And pattern matching give us the ability to name things on-the-fly, more or less the equivalent of defining a local variable in e.g. Java. So, as I was saying before I so rudely interrupted myself…

For a non-empty string s, the result is a word followed by the words from the rest of the string, where those two things (word and rest) are constructed by breaking s at the first space (the first character for which the function isSpace returns true). The single-colon is often read as “cons”, in homage to Lisp. It constructs a list (of some type) by gluing a value (of the correct type) onto the beginning of a list (of the same type). Becuase word is a String and words rest is a list of String, the entire expression word : words rest is also a list of String.

Notice that both dropWhile and break have two arguments: another function (isSpace in both uses here) and a list. This works because dropWhile and break are higher-order functions, which take functions as arguments and use them whenever needed. If you cross your eyes and squint a little, this begins to look like design patterns in OO.

---