On Haskell, Intuition And Expressive Power

Introduction

An imperative programmer learning Haskell goes through a number of stages. One of these stages is frustration with perceived lack of productivity. I say perceived because the feeling is fraudulent - basic qualitative analysis a little bit of thinking¹ reveals that in this case human intuition is inconsistent with reality. Confused? Allow me to explain.

This stage hits you by surprise. With some persistence you inevitably get good enough to be able read, write, and understand Haskell programs and decide to write something relatively big in Haskell yourself. At some point you catch yourself staring at the screen and realize that you haven't typed a single character in many minutes. Not because you're procrastinating or daydreaming - you are thinking about the problem. And not because you don't know how to do something in Haskell - you do know. After a while you realize that this happens more and more often, in fact, it's the usual state of affairs when programming in Haskell. This results in a very frustrating experience - an imperative programmer's intuition tells you aren't being productive.

It takes quite a bit of time to get used to the idea that more thinking and less typing is a blessing rather than a curse. You don't stop typing for minutes at a time because you're not being productive. You stop typing because Haskell is incredibly expressive - one line of Haskell code is often equivalent to dozens of lines of Java or C++. You end up spending almost the same amount of time thinking about the problem regardless of the language but with Haskell you spend a lot less time (and space) expressing the problem in terms a computer can understand.

Expressive Power

Here's an example from something I've been doing for a prototype of a web application. This piece of code goes through a parse tree of Haskell source code, locates every reference to an identifier that ends with "Widget", puts it on a list, and removes duplicates so every identifier is represented in the list only once. I did this to avoid writing boilerplate code every time I create a new servlet.

extractWidgets :: (Data a) => a -> [String]
extractWidgets = nub . map (\(HsIdent a)->a) . listify isWidget
    where isWidget (HsIdent actionName)
              | "Widget" `isSuffixOf` actionName = True
          isWidget _ = False
          

It took me quite a bit of time to write this piece of code. Considering how long it took to write these five lines² it may seem that I wasn't very productive. However, if we consider how much this tiny paragraph of code does, a different picture begins to emerge.

Let's see. The first line tells Haskell that extractWidgets should accept one argument of any type (that's what lowercase a means), and should return a list of strings. (Data a) says that only types that belong to a class Data should be accepted for the first parameter. This is Haskell's way of saying that no matter what type is passed to extractWidgets it must expose an interface defined by Data. This property will be verified by Haskell at compile time.

The dots in the second line suggest that we should read it from right to left. The rightmost expression (listify isWidget) returns a function that takes a single argument. Whenever someone will call extractWidgets with an argument, this argument will really be passed to a function returned by listify (this is currying at work). At this point this function will examine this argument, iterate through its terms (sort of like reflection can iterate through member fields), and will call isWidget on each term only if the type of that term is the same as the type isWidget accepts (this type happens to be HsName and the compiler will infer it automatically). The function will return a list of all terms for which isWidget returns true. We'll get to the definition of isWidget in a little bit, but on a high level it checks whether an identifier ends with the string "Widget". Haskell will then apply the expression between the dots (map (\(HsIdent a)->a)) to the list returned by the function described above. In functional programming map is like a foreach - it iterates (maps) over a collection, applies a function passed to it to each element of the collection, and returns a new collection with transformed elements. In our case map maps through all the identifiers that end with "Widget" (that's what the rightmost expression returns, remember?) and applies a function that simply converts HsIdent to String so we get a list of strings as a result. The function to do that ((HsIdent a)->a) is so simple that we don't need to give it a name - we simply create it inline via \ - Haskell's operator to create unnamed (lambda) functions. Finally we take this list and pass it to the first expression on the line - a function called nub. Now, what in the name of all holy is nub? Here's where Haskell shines - not only does it teach you functional programming, but also some vocabulary! Dictionary.com defines nub as "the point, gist". The function returns the gist of the list, which amounts to the list with duplicates removed so every item appears on the list only once.

The last three lines actually define the function isWidget. Keyword where means that the function is local to extractWidgets - it will not be seen by any other function. As you already know isWidget takes one parameter, but not just any parameter. We're only interested in the ones that have a type of HsName. Now, Haskell names may take shape of identifiers and symbols. For the purposes of this exercise we're only interested in identifiers and we specify that by matching the argument against a pattern (HsIdent actionName). If the pattern matches, Haskell goes on to check the guard specified by | "Widget" `isSuffixOf` actionName. This is like an if statement that checks whether "Widget" is a suffix of actionName. If and only if the pattern and the guard both pass, does the function return True. In all other cases it returns False. Note that we match all other cases via a pattern _. This way we tell Haskell that we don't care what the argument is, we already know we need to return False, but we could easily add more patterns and guards if we needed to.

It's also interesting to note why isSuffixOf is wrapped in back quotes. In Haskell every binary function may be used with regular prefix syntax (isSuffixOf "Widget" actionName) or as an operator ("Widget" `isSuffixOf` actionName). The latter is accomplished by wrapping the function with back quotes. In this case using isSuffixOf as an operator simply makes the code more clear.

The Challenge

Imagine that you're writing a method that receives a JavaCC parse tree of Java source code and you're trying to accomplish the task outlined at the beginning of the previous section. You have many options to go about solving this problem and all of them will result in code much longer than the five lines presented above. You will likely spend much more time than I did in order to do it in Java, your code will be harder to read, less abstract, more error prone (Java's type system simply lacks the expressive power to represent and verify something like listify at compile time³), and harder to maintain. But look on the bright side. You'll sure do a lot more typing!

Go ahead, give it a try. The first guy to write a complete Java method that does this in five lines or less of reasonably normal looking Java code⁴ gets a free (as in beer) book of his choice:

Challenge Update

The challenge was won by Jonathan "nostrademons" Tang. He emailed me his solution only a few hours after I published the article. While the solution doesn't meet the rules of the challenge to the letter, in my opinion it is close enough to declare Jonathan a winner. I fully reproduce his post with the solution here. I encourage everyone to examine it - it perfectly highlights the differences between Java and Haskell programming styles. Note that the Haskell solution is significantly more maintainable - it does not depend on the parser's data structures or a particular method of iteration. It only depends on a single data structure of interest - the one that represents the symbol. Congrats to Jonathan for winning a copy of To Mock a Mockingbird.

Updated: 12/18/2006

Comments?

If you have any questions, comments, or suggestions, please drop a note at . I'll be glad to hear your feedback.

extractWidgets :: (Data a) => a -> [String]
extractWidgets = nub . map (\(HsIdent a)->a) . listify isWidget
    where isWidget (HsIdent actionName) = "Widget" `isSuffixOf` actionName
          isWidget _ = False