Lambda the Ultimate

       four
  add  four
equals eight

It's pretty much exactly equivalent to the usual notation, except that it's much harder for us to read, not at least partly because it's so verbose. I'm sure part of what makes Haskell so appealing to some programmers is how concise it is. And it achieves much of that syntactic parsimony through the heavy use of symbols. A more verbose Ada-like dialect of Haskell where all the symbols are replaced by word tokens would probably cause FP programmers to recoil in horror.

I would argue that choosing to *not* include operator overloading was one of the biggest failures of Java's design, and is why it would be utter folly to even attempt to implement half the libraries that exist for C++, including Spirit++, Blitz++, Boost.Iterator, etc. Sometimes I look upon libraries like Boost.Lambda with a combination of admiration and loathing, but you have to admit that for a 20 year old statically typed imperative PL, C++ does all right for itself.

A more verbose Ada-like dialect of Haskell where all the symbols are replaced by word tokens would probably cause FP programmers to recoil in horror.

You mean like Scheme...? ;)

I'm all for judicious use of operator overloading, but I think it a mistake to assume that the elegance of the Haskell code is due to operators. The use of operators in the Haskell code is pretty bare minimum and there's nothing particularly out of the ordinary for those that are used ([] : * = ==

So the question back is why is the Haskell code considered elegant? FWIW, the Oz code and the Alice ML code are fairly close to the Haskell code, so perhaps the answer is not the Haskell Type system. For sure, you have to have lazy functions. (IMHO, any solution that uses iteration and array pointers misses the whole point to the elegance of the recursion).

As an aside, APL has always been on the extreme in terms of usage of operators. For those that understand the symbols, APL provides a power for manipulation that is as expressive as any language. For those that don't understand the symbols, APL can look like chicken scratch. The biggest problem with APL is that you can't define new operators that act in a first class fashion.

The use of symbols in code can sometimes aide readibility. It can also sometimes make it harder to grok. Not particularly caring about C++ at this juncture in history, I find it weird that the use of such symbols as >> and

The use of operators in the Haskell code is pretty bare minimum and there's nothing particularly out of the ordinary for those that are used ([] : * = ==

In that example, although Haskell uses a lot more symbols than that. But perhaps another major source of conciseness is the type inference. That takes a *lot* of identifiers out of the code that you find in manifestly typed languages.

The use of symbols in code can sometimes aide readibility. It can also sometimes make it harder to grok.

Can we say: "awk/sed"?

Not particularly caring about C++ at this juncture in history, I find it weird that the use of such symbols as >> and

Well, I've never understood this criticism of C++. If you want to concatenate stream operations, you need to have a stream operator. Was there some de facto stream operator before ? It makes perfect sense to me, since most *nix shells use > and .

I was way too harsh and vague in my comment about "bad code". Excuse me, I'll try not to do this in the future.

I'll try to explain my point in some more detail, if you're still listening...

I easily grant that, given any concrete task, C++ can be made as expressive as Haskell for this task, by writing a (quite large) supporting combinator library (operator overloading and expression templates to build/evaluate syntax trees).

But the "bad code" I blurted out isn't just an expressivity measure. The criterion of "good code" I have developed over the years is as follows: good code should be right, and it should be obviously right.

Of course, there are different grades of "obviously", so it's a very subjective metric. But the experience of many people shows that it's VERY hard to write "obviously right" code in C++.

For a quick mental test, look back at the code you supplied (_if, _1, _2 and stuff). Imagine debugging/maintaining just a couple hundred lines of such code, freely mixed with "normal" C++ and - for kicks - also using some other expression-template combinator library (e.g. Boost Spirit).

I can easily imagine working with tasks of similar complexity in Haskell - though I'm a Haskell newbie at best.

And no, operator overloading isn't the biggie here. It's just syntax.

For example: you alluded to my mock Java sample as "stupid", but... dont' you think that, if you're embedding a functional language within C++, you're going to need a garbage collector at some point? Yes, value types help, but they don't solve all problems. OCaml has a GC. Haskell has a GC. And even Java has a GC... so my example wasn't so stupid after all :-)

See? This semantic issue is much more important than the syntax issue (operator overloading) you pointed out.

For example: you alluded to my mock Java sample as "stupid", but... dont' you think that, if you're embedding a functional language within C++, you're going to need a garbage collector at some point? Yes, value types help, but they don't solve all problems. OCaml has a GC. Haskell has a GC. And even Java has a GC... so my example wasn't so stupid after all :-)

Well, the most important value type in C++ is the smart pointer. ;> Not only can you use vanilla strategies like reference counting, you can use a good smart pointer framework to implement a garbage-collected pointer. Of course, if you absolutely must have a "pure" garbage collector, you can just link one in to the C++ program as well. Not only does C++ come with the kitchen sink, it comes with an optional garbage disposal too! ;>

Okay, that is a challenge. :)

def scale(n, it):
    for e in it: yield n * e

def cons(x, it):
    yield x
    for e in it: yield e

def merge(xs, ys):
    x, y = xs.next(), ys.next()
    if x == y:
        for e in cons(x, merge(xs, ys)): yield e
    elif x 

This basically follows the Haskell version point for point except that it's done using generators and iterator algebra (by the way, the above merge function only works with infinite iterators since it doesn't catch StopIteration).

>>> from itertools import izip
>>> for i, e in izip(range(100000), seq()):
...   if i % 10000 == 0:
...     print i, e
... 
0 1
Traceback (most recent call last):
  File "", line 1, in ?
  File "", line 3, in seq
<snip />
  File "", line 3, in cons
  File "", line 2, in merge
RuntimeError: maximum recursion depth exceeded

To be fair to Python, a nice fast working solution is in here, from a thread previously referenced in this topic.

The Haskell version has the same number of recursions as my Python version, up to a constant factor. None of the recursions in either version are in tail call position, so they cannot be optimized away. So as far as expressivity at the language level is concerned, I don't think the maximum recursion depth bail-out is very relevant--if you tested it on Stackless (or any other Python implementation with a priori unbounded call stack) there would be no issue aside from performance (a function call in Python is at least two heap allocations).

By the way, I wasn't trying to present my code as "the best" or whatever, I just wrote it up to see how close to the spirit of the Haskell code I could get without doing any insane stunts. I figured I might as well share it.

The Haskell version has the same number of recursions as my Python version, up to a constant factor.

I'm just a casual Python user, but it seems to me that your version starts new generators for each recursive call to seq(), whereas the Haskell version shares the ham list.

None of the recursions in either version are in tail call position [..]

But the recursive calls of ham are on lazy positions and the Haskell program only needs constant stack space.

You're absolutely right, that's what I get for only being a casual Haskell user (if even that). Oh well.

Under Scala 2.6 / Sun JDK 1.6.0_02:

$ sudo rpm -ivh http://www.scala-lang.org/downloads/distrib/files/scala-2.6.1-1.i386.rpm

$ java -version
java version "1.6.0_02"
Java(TM) SE Runtime Environment (build 1.6.0_02-b05)
Java HotSpot(TM) 64-Bit Server VM (build 1.6.0_02-b05, mixed mode)

$ cat -n hamming.scala | head -14 | tail -3
    12        if (cmp == 0) Stream.cons(x, merge(xs.tail, ys.tail))
    13        else if (cmp < 0) Stream.cons(x, merge(xs.tail, ys))
    14        else Stream.cons(y, merge(xs, ys.tail))

$ time scalac hamming.scala

real    0m4.721s
user    0m4.296s
sys     0m0.169s

$ time scala hamming
The first 20 numbers:
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36

The 100th number (counting from 0): 1600

The 1000th:
java.lang.OutOfMemoryError: Java heap space
        at scala.Stream$cons$.apply(Stream.scala:45)
        at hamming$.merge(hamming.scala:14)
        at hamming$$anonfun$merge$1.apply(hamming.scala:12)
        at hamming$$anonfun$merge$1.apply(hamming.scala:12)
        at scala.Stream$cons$$anon$2.tail(Stream.scala:52)
        at scala.Stream$$anonfun$map$1.apply(Stream.scala:340)
        at scala.Stream$$anonfun$map$1.apply(Stream.scala:340)
        at scala.Stream$cons$$anon$2.tail(Stream.scala:52)
        at hamming$$anonfun$merge$3.apply(hamming.scala:14)
        at hamming$$anonfun$merge$3.apply(hamming.scala:14)
        at scala.Stream$cons$$anon$2.tail(Stream.scala:52)
        at hamming$$anonfun$merge$1.apply(hamming.scala:12)
        at hamming$$anonfun$merge$1.apply(hamming.scala:12)
        at scala.Stream$cons$$anon$2.tail(Stream.scala:52)
        at scala.Stream$$anonfun$map$1.apply(Stream.scala:340)
        at scala.Stream$$anonfun$map$1.apply(Stream.scala:340)
        at scala.Stream$cons$$anon$2.tail(Stream.scala:52)
        at hamming$$anonfun$merge$1.apply(hamming.scala:12)
        at hamming$$anonfun$merge$1.apply(hamming.scala:12)
        at scala.Stream$cons$$anon$2.tail(Stream.scala:52)
        at scala.Stream$$anonfun$map$1.apply(Stream.scala:340)
        at scala.Stream$$anonfun$map$1.apply(Stream.scala:340)
        at scala.Stream$cons$$anon$2.tail(Stream.scala:52)
        at hamming$$anonfun$merge$1.apply(hamming.scala:12)
        at hamming$$anonfun$merge$1.apply(hamming.scala:12)
        at scala.Stream$cons$$anon$2.tail(Stream.scala:52)
        at scala.Stream$$anonfun$map$1.apply(Stream.scala:340)
        at scala.Stream$$anonfun$map$1.apply(Stream.scala:340)
        at scala.Stream$cons$$anon$2.tail(Stream.scala:52)
        at hamming$$anonfun$merge$3.apply(hamming.scala:14)
        at hamming$$anonfun$merge$3.apply(hamming.scala:14)
        at scala.Stream$cons$$anon$2.tail(Stream.scala:52)

real    0m26.626s
user    0m24.523s
sys     0m0.520s

Will try again in a couple of years.

Note to self regarding comment-38966:

$ time /var/tmp/scala-2.8.1.final/bin/scala hamming
The first 20 numbers:
1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 25, 27, 30, 32, 36

The 100th number (counting from 0): 1600

The 1000th:
java.lang.OutOfMemoryError: Java heap space
    at java.util.Arrays.copyOfRange(Arrays.java:3137)
    at java.math.BigInteger.trustedStripLeadingZeroInts(BigInteger.java:2792)
    at java.math.BigInteger.multiply(BigInteger.java:1144)
    at hamming$$anonfun$seq$1$$anonfun$apply$1.apply(hamming.scala:19)
    at hamming$$anonfun$seq$1$$anonfun$apply$1.apply(hamming.scala:19)
    at scala.collection.immutable.Stream$$anonfun$map$1.apply(Stream.scala:168)
    at scala.collection.immutable.Stream$$anonfun$map$1.apply(Stream.scala:168)
    at scala.collection.immutable.Stream$Cons.tail(Stream.scala:565)
    at scala.collection.immutable.Stream$Cons.tail(Stream.scala:557)
    at hamming$$anonfun$merge$1.apply(hamming.scala:12)
    at hamming$$anonfun$merge$1.apply(hamming.scala:12)
    at scala.collection.immutable.Stream$Cons.tail(Stream.scala:565)
    at scala.collection.immutable.Stream$Cons.tail(Stream.scala:557)
    at scala.collection.immutable.Stream$$anonfun$map$1.apply(Stream.scala:168)
    at scala.collection.immutable.Stream$$anonfun$map$1.apply(Stream.scala:168)
    at scala.collection.immutable.Stream$Cons.tail(Stream.scala:565)
    at scala.collection.immutable.Stream$Cons.tail(Stream.scala:557)
    at hamming$$anonfun$merge$1.apply(hamming.scala:12)
    at hamming$$anonfun$merge$1.apply(hamming.scala:12)
    at scala.collection.immutable.Stream$Cons.tail(Stream.scala:565)
    at scala.collection.immutable.Stream$Cons.tail(Stream.scala:557)
    at scala.collection.immutable.Stream$$anonfun$map$1.apply(Stream.scala:168)
    at scala.collection.immutable.Stream$$anonfun$map$1.apply(Stream.scala:168)
    at scala.collection.immutable.Stream$Cons.tail(Stream.scala:565)
    at scala.collection.immutable.Stream$Cons.tail(Stream.scala:557)
    at hamming$$anonfun$merge$1.apply(hamming.scala:12)
    at hamming$$anonfun$merge$1.apply(hamming.scala:12)
    at scala.collection.immutable.Stream$Cons.tail(Stream.scala:565)
    at scala.collection.immutable.Stream$Cons.tail(Stream.scala:557)
    at scala.collection.immutable.Stream$$anonfun$map$1.apply(Stream.scala:168)
    at scala.collection.immutable.Stream$$anonfun$map$1.apply(Stream.scala:168)
    at scala.collection.immutable.Stream$Cons.tail(Stream.scala:565)

real    0m25.552s
user    0m25.692s
sys     0m0.919s