Lambda the Ultimate

The April issue of C/C++ Users Journal has an article called A New Solution To an Old Problem by Andrew Koenig and Barbara E. Moo. In it, they revisit the Hamming numbers problem from Dijkstra's A Discipline of Programming.

They examine four different solutions:

1. A naive O(n^2) solution.
2. Dijkstra's efficient but somewhat convoluted O(n) solution (re)implemented in C++.
3. An elegant O(n) solution in Haskell.
4. Their own new O(n*log(n)) solution in "idiomatic C++".

The Haskell solution is the following

scale n (x:xs) = (n * x) : (scale n xs)
merge xs [] = xs
merge [] ys = ys
merge (x:xs) (y:ys) =
   if x == y then
      x : (merge xs ys)
   else if x < y then
      x : (merge xs (y:ys))
   else
      y : (merge (x:xs) ys)

seq = 1 : (merge (scale 2 seq)
                 (merge (scale 3 seq) (scale 5 seq)))

Their "idiomatic C++" solution uses ordered sets:

set<int> seq;
seq.insert(1);
set<int>::const_iterator it = seq.begin();

int val = *it;
seq.insert(val * 2);
seq.insert(val * 3);
seq.insert(val * 5);
it++;

In conclusion, they have this to say (emphasis mine),

We have looked at four solutions to a simple problem. The first was straightforward but slow. The second was much faster but fairly tricky. The third, in a functional language, was again straightforward -- but requires a totally different way of thinking about programming. Indeed, advocates of this way of thinking use the program's straightforwardness to argue that this way of thinking is superior.

With the fourth solution, we believe that the argument is far from obvious.

I may be reading too much into this quote, but it sounds to me like Koenig and Moo consider it a bad thing to require a "totally different way of thinking about programming".

P.S. While googling for Hamming numbers, I came across this related paper: Expressivity of Functional-Logic Languages and Their Implementation by Juan José Moreno Navarro.