Evan Martin (evan) wrote in evan_tech,
Evan Martin

haskell pattern: function composition

I've read (somewhere, and phrased better than I can) that Haskell operates over functions in the way Perl munges text. I'm not sure if that's really captures it. Another way of looking at it is that they use functions as their fundamental unit of thought, in the way that Lisp uses lists and Smalltalk uses objects. Much like in those other languages, using a unifying concept pervasively means you get a consistent set of operators and patterns in every part of the language, and it often allows discrete pieces to combine in interesting ways. This is also part of why Haskell syntax is so sparse: function operations are written very simply and most of the code is functions.

Here's an example illustrating one of my favorite ways this works out. In the game Diplomacy you refer to place names, like "St Petersburg", by using short three-letter identifiers for those place names ("stp"). The rules for shortening are pretty intuitive (that example ought to suffice). Let's write a function that maps long place names to short ones.

One piece is lowercasing a string, which we can call lowercase. Strings are lists of characters, so you can use map to apply the character function toLower to each letter in the string:
lowercase str = map toLower str
This is old hat. Here's the new part: (simplifying a bit,) by leaving out an argument, you leave a "hole" that can be filled in by an argument that can be supplied later. Here's an equivalent definition of lowercase:
lowercase = map toLower
You can look at that as saying "the operation of lowercasing something is just mapping toLower over it". This just looks like a cute trick, but bear with me.

Now consider removing spaces from a string. There's a standard function "filter" that filters out all elements from a list that pass a test. Not-equals is written as /= (think like in math), and is a function that takes two arguments; using the previous trick, we write (/= ' ') to get a function that takes one argument: this new function returns true if its argument is not a space. So then we can define, again following the lowercase pattern:
withoutSpaces = filter (/= ' ')
"removing spaces is defined as filtering out everything that isn't a space".

Finally, there's a standard function called take: take 3 list gives you the first 3 elements of list.

So the final function applies each of these in a row.

Here's one more piece: function composition is written with a period, again simulating the circle operator in math:
(f ∘ g)(x) = f(g(x))

So here's a nice final version of the function (and legal Haskell code):
shorten = take 3 . withoutSpaces . lowercase
  where withoutSpaces = filter (/= ' ')
        lowercase = map toLower

There are two primary reasons I like this:
  1. The code is quite succinct and readable directly, and not because of any cute naming tricks. "Shortening is taking 3 characters, removing spaces, and lowercasing. Removing spaces is keeping everything that's not a space; lowercasing is lowercasing each character." There are no regular expressions, list subscripts, blocks, and even:
  2. there are no variables. This problem has been lifted from an operation over characters and strings to the higher level of an operation over functions.
This latter transformation is called pointfree and is discussed in more interesting detail on that page.
Tags: haskell
  • Post a new comment


    default userpic
    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.