I’d like to revisit the discrete convolution problem described in my previous post, to consider the expressiveness of functional programming. Here I am interested in the power of code to communicate intent; the bare metal speed of the code is secondary.

The various comments and proposed implementations in this Google Groups thread are what got me thinking about this. My thanks to all the contributors. I’ll begin by quoting some imperative code posted to the thread:

The code is brief, and the style is familiar to most programmers. But it is all how, and no what. I look at it, and I do not see what it means. This proposed solution to an inherently mathematical problem make no use of mathematical constructs other than addition and subtraction. I think this is a shame, since convolution has a mathematical structure. A convolution is a sequence of inner products:

My proposed solution is longer than the imperative solution, but not much longer. And I should not have had to write inner-product; the inner product is so fundamental a mathematical operation that it should be part of every language.

I believe conv describes convolution more clearly than does convolve, because it does so in terms of operations on mathematical structures rather than as the outcome of changes to the contents of computer memory.

It also seems to me that convolve overspecifies the solution. The introduction of loops and mutation imposes a sequential structure on the solution that is not present in the underlying mathematics. For some fascinating thoughts along those lines I highly recommend Guy Steele’s ICFP 2009 presentation. It is an eye-opener.

While I’m ranting, I don’t think I should have had to write the tails function either, at least in so naked a form. The notion of an iterated function deserves a place in a functional programming language. I think Clojure is missing something along the lines of nest-list (stolen from Mathematica’s NestList).

Postscript: a few days later, while browsing core.clj, I noticed that Clojure already has the function iteration feature I wanted, it is called iterate. The implementation is quite pretty, much nicer than what I came up with: