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
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.)
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
Stringcan 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
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 (
rest) are constructed by
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
words rest is a list of
String, the entire expression
word : words rest is also a list of
Notice that both
break have two arguments: another function (
isSpace in both uses here) and a list. This works because
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.