Javascript functional lazy evaluation example explanation required

Question

Browsing Hacker News and I come across http://streamjs.org/ which is an implementation of a lazy evaluated collection in Javascript.

One of the examples is this:

function ones() {  
    return new Stream( 1, ones );  
}  
function naturalNumbers() {  
    return new Stream(  
        // the natural numbers are the stream whose first element is 1...  
        1,  
        function () {  
            // and the rest are the natural numbers all incremented by one  
            // which is obtained by adding the stream of natural numbers...  
            // 1, 2, 3, 4, 5, ...  
            // to the infinite stream of ones...  
            // 1, 1, 1, 1, 1, ...  
            // yielding...  
            // 2, 3, 4, 5, 6, ...  
            // which indeed are the REST of the natural numbers after one  
            return ones().add( naturalNumbers() );  
        }   
    );  
}  
naturalNumbers().take( 5 ).print(); // prints 1, 2, 3, 4, 5

Perhaps it's too late at night and I'm missing the point, but I don't understand how this prints 1,2,3,4,5. I would expect it to print 1,2,2,2,2 and die of infinitely deep recursion. I understand how ones will print infinite 1. I don't get how naturalNumbers works.

By my (evidently incorrect) logic, the head of the Stream returned by the first call to naturalNumbers will be 1, and the next element in the stream is evaluated as ones().add( naturalNumbers() ); which is ones().add(1) followed by ones().add( naturalNumbers() ) which will reeavulate to 1 and so on...

Would really appreciate it if someone would shed some light on this.

Answer 1

naturalNumbers[0] = 1 // by definition
naturalNumbers[1] = ones[0] + naturalNumbers[0] = 1 + 1 = 2
naturalNumbers[2] = ones[1] + naturalNumbers[1] = 1 + 2 = 3
naturalNumbers[3] = ones[2] + naturalNumbers[2] = 1 + 3 = 4
...

The crucial point is that function() { return ones().add(naturalNumbers()) } does not return an element, it returns a stream. Subsequent elements are generated by that stream, a "summing" stream in this case. Thus, unlike ones(), naturalNumbers() does not invoke itself directly. Rather, it invokes itself indirectly -- mediated by the summing stream.

Answer 2

Ok, I'll take this on :)

ones is the easy starting point. This function returns a Stream whose first value is 1, and whose remaining values can be calulated by invoking the ones function itself. So any request for the 'rest' of one's values will always start with 1, ad infinitum.

The next thing to look at is the take function:

function (howmany) {
    if (this.empty()) {
        return this;
    }
    if (howmany == 0) {
        return new Stream;
    }
    var self = this;
    return new Stream(this.head(), function () {
        return self.tail().take(howmany - 1);
    });
}

So from the top to the bottom, if the Stream is empty then it doesn't matter how many items were requested as that request can't be fulfilled, so the Stream returns its (empty) self.

If we've requested no items, i.e. howmany == 0, then an empty Stream is returned, which itself will yield no items if asked.

Lastly is the fun part. A reference to the current Stream is locked into the function scope and a new Stream is returned. This new Stream is created with the same head as the current Stream, and whose tail is created by a function that will take one less item from the original Stream's tail than the caller requested. So as the head is one item and the tail can generate howmany-1 items, the caller will receive a new Stream with the potential to deliver the requested number of items.

The naturalNumbers are a bit more tricky.

The naturalNumbers function returns a Stream that has 1 as its head, and an inner function to generate its tail.

The inner function returns the result of calling the add method on the ones Stream, with the result of calling the naturalNumbers function. So we can guess that this involves 'pairing' two Streams together in some way.

What does add look like? It's a function that is passed a Stream:

function (s) {
    return this.zip(function (x, y) {
        return x + y;
    }, s);
}

We can recognise the 'add' part as the inner function - it's adding two values together, so that makes sense. But what does zip do? zip is a function that takes a function and a Stream as parameters.

function (f, s) {
    if (this.empty()) {
        return s;
    }
    if (s.empty()) {
        return this;
    }
    var self = this;
    return new Stream(f(s.head(), this.head()), function () {
        return self.tail().zip(f, s.tail());
    });
}

So in the case of add, the function passed in was the 'add' (x+y) function, and the Stream was the naturalNumbers Stream.

What does zip do with these values? If the Stream itself is empty, the the 'other' Stream is returned. I guess this is because adding [] to [2,4,6,8,...] makes more sense to be [2,3,6,8,...] than anything else. i.e. the first Stream is treated as infinitely many 0 or "".

If the passed-in Stream is empty, then the same rule as above applies, just in reverse. i.e. adding [2,4,6,8,...] to [].

Now the fun part. After capturing a reference to itself, a new Stream is returned. This Stream is made up of a head value which is the 'add' function applied to the head elements of each Stream and a function that will apply the 'add' function to the tail of each Stream if required.

So in the case of ones().add(naturalNumbers()), this would result in a Stream whose head is 2, as the 'add' function is called with 1 and 1 (the head element of both ones and naturalNumbers are both 1). So if this new Stream is asked to be added to ones, then it will be ones head element (always 1) added to the new Stream's head element (now 2), giving 3.

The tail of this new Stream is a mechanism to deliver more 'adds' if required.

So what we are left with is basically a way of describing operations to be applied to head elements and the tail. Only when we come to ask for a particular number of items do we go through the machinery to generate those items.

So if you called ones().take(9999999999999999999999999999999).print() then it would take a lot of resources as the print function needs to have the value before it can print it - it necessarily causes this machinery to have to deliver that many 1s. But ones().take(9999999999999999999999999999999) on its own is just a description of the head element 1 and a process to deliver the rest of the items, but only if asked for.

But... I could have got that completely wrong as it's late for me too and I've only just read the article ;)

Answer 3

Just carry out the evaluations one term at a time:

ones
= { 1, ones }
= { 1, { 1, ones } }
= ...
= { 1, { 1, { 1, ... to infinity!

nat
= { 1, ones+nat }
= { 1, { 1, ones } + { 1, ones+nat } } = { 1, { 1+1, ones+ones+nat } }
= { 1, { 2, { 1, ones } + { 1, ones } + { 1, nat } } }
= ...
= { 1, { 2, { 3, ... and so on.

The "sieve" example at the botton of http://streamjs.org is even more mind-twisting, try it!