Hamming numbers

Searching for Ada and coroutines I've stumbled on this news thread. They are talking about generators, among the other things. Paul Rubin shows how expressive and concise Haskell can be.

The code he shows computes Hamming numbers in few lines of elegant code (this should be an implementation of Dijkstra's algorithm). Here's the code:

hamming = 1 : m 2 `merge` m 3 `merge` m 5 where
  m k = map (k *) hamming

xxs@(x:xs) `merge` yys@(y:ys) = case x `compare` y of
  LT -> x : (xs `merge` yys)
  EQ -> x : (xs `merge` ys)
  GT -> y : (xxs `merge` ys)

main = print (hamming !! 1499)

Anyway, Paul Rubin states:

I remember doing it in C++ and it was a page or so of ugly code.

I wonder why it should be so. But I'm too lazy to make my own attempt, so I've checked on Rosetta Code, because it's the typical task you can find there.

On the task page Hamming numbers you can see a possible solution in C++ and alternative solutions in Haskell, and other languages. The first Haskell implementation is the “classic version”, the one given by Rubin too, but other algorithms exist and they could be a better fit for other languages.

Disregarding which algorithm is used in the first implementation, C++ isn't so bad; but the C++ solution which is allegedly a translation of one of the given Haskell solutions is, in fact, very much longer and less expressive than Haskell solution. Maybe because of the implementation of the LazyList, something which Haskell has natively.

There are other languages which have nice and/or not so long implementation, or just more interesting/efficient algorithms; e.g., for reasons I don't always explain:

• AWK, this procedural language shows that Haskell's “elegance” is show off which fits Dijkstra's algorithm¹… The computation of 1691 (and hence 1499) isn't a problem with a different approach, though it is indeed slower (0.031s of real time). The same idea is used also in bc, and it can be used in other procedural languages resulting in concise code.
• Clojure, which implements Dijkstra's merge solution, to be compared to Haskell.
• Go section has a “Low Memory Use Enumerating Version Eliminating Duplicates” implementation, which translates Haskell implementing lazy lists as in the C++ case, but it has also a “Fast imperative version avoiding duplicates, reducing memory, and using logarithmic representation” solution.
• Julia, interesting…
• Octave as Julia: interesting².
• Oz (an underestimated and mostly unknown language).
• Perl6
• Racket
• Ruby, slow but nice.
• Tcl the slow version uses coroutines…

Ada isn't among those languages that shine for conciseness or expressiveness, that's for sure, and it is also slow (I've interrupted the computation for 1691 — AWK did it…) Likely a better implementation is possible.

---

1. It is made clear also in the Wikipedia page: Dijkstra's “algorithm is often used to demonstrate the power of a lazy functional programming language”. Hence, of course non-lazy, non-functional language can't implement this algorithm as well as functional lazy language. (Or just functional: I think the lazy part affects efficiency, not expressiveness.)↩

2. I think the same idea can be implemented in Fortran.↩