The other day, I was thinking about some code in a domain that I used to do a lot of work in: signal filtering. Imagine that you have an array of doubles and you want to remove some of its spikiness. One way to handle this is to use a low pass filter. You take your old array and transform it into a new one in which each element array[i] has the value (old_array[i-1] + 2 * old_array[i] + old_array[i + 1]) / 4.0. The code for that filter is straightforward except for the fact that you have to deal with the edge cases: the calculations for i = 0 and i = n - 1 are a little different. All in all, it's about five to seven lines of code, depending upon how you format it.

For kicks, I decided to write it in Haskell. If I'm clever enough, I thought, I should be able to write the code without any edge conditions. I can create a lazy list that goes beyond the edges and then pick out the subset that I need from the center.. the values in the range 0..n-1.

I ended up with a solution but it wasn't pleasant, so I posted it to the Haskell Cafe mailing list. A guy who knows much more Haskell than I do pulled an edge case back in and came up with this shorter solution:

smooth n = (!! n) . iterate f where
  f ds = [(x + 2 * y + g y z) / 4.0 | x:y:z <- tails (head ds : ds)]
  g x []    = x
  g _ (x:_) = x

The function smooth allows you to smooth a list n times. It does this by creating an infinite list of iterative applications of a low pass filter and selecting the nth element of that list. The function that is iterated, f, constructs a list of elements which are applications of the filter (x[i-1] + * 2.0 x[i] + x[i+1] / 4.0). The smooth function also uses a list comprehension that matches triples based upon the staggered tails of a the original list. The special case at the far end of the list is handled by a function, g, which takes an element and a list and returns the appropriate values at the edge for the filter.

Simple, right?

It depends on your perspective, I guess. There is some simplicity there if you think in those terms.

To me, this problem seems emblematic of the difference between imperative and functional programming. In functional programming, some solutions are very natural when seen from the imperative mindset, but others aren't - you have you go around the block to get next door. Functional programming has a grain to it and the grain makes particular classes of solutions much more natural even though they appear alien when seen from other contexts.

I guess this is true of all styles of programming. There certainly are some problems that are difficult in an imperative style. The thing that I find interesting about the pure functional style, though, is that it pushes you toward its own set of abstractions. The function tails in the code above is a good example. If you give tails this list: [1,2,3] it gives you this list back: [[1,2,3],[2,3],[3],[]]. I doubt many people using a non-functional language could imagine many uses for a function like that, but when the grain runs toward laziness and away from mutation, you reach for these sorts of abstractions for leverage - they become your bread and butter.

Haskell truly is a different language. It makes most other programming languages look like dialects of each other.