owlishDeveloper owlishDeveloper - 4 months ago 25
Javascript Question

Eloquent JavaScript, Sequence Interface

I am working my way through Eloquent JavaScript, and I am having questions about problem #6.3 (second edition).

Here is the problem:


Design an interface that abstracts iteration over a collection of
values. An object that provides this interface represents a sequence,
and the interface must somehow make it possible for code that uses
such an object to iterate over the sequence, looking at the element
values it is made up of and having some way to find out when the end
of the sequence is reached.

When you have specified your interface, try to write a function
logFive that takes a sequence object and calls console.log on its
first five elements—or fewer, if the sequence has fewer than five
elements.

Then implement an object type ArraySeq that wraps an array and allows
iteration over the array using the interface you designed. Implement
another object type RangeSeq that iterates over a range of integers
(taking from and to arguments to its constructor) instead.


I wrote this solution:

function ArraySeq(collection) {
this.values = collection;
}

ArraySeq.prototype.iterate = function(start, end, action) {
var n = Math.min(this.values.length, end);
for (var i = start; i < n; i++) {
action(this.values[i]);
}
};

function RangeSeq(from, to) {
var array = [];
for (var i = from; i <= to; i++)
array.push(i);
ArraySeq.call(this, array);
}

RangeSeq.prototype = Object.create(ArraySeq.prototype);

function logFive(sequenceObject) {
sequenceObject.iterate(0, 5, console.log);
}

//This code to test how the solution works was provided by the author
logFive(new ArraySeq([1, 2]));
// → 1
// → 2
logFive(new RangeSeq(100, 1000));
// → 100
// → 101
// → 102
// → 103
// → 104


The solutions by the author are different, here are both of them:

// I am going to use a system where a sequence object has two methods:
//
// * next(), which returns a boolean indicating whether there are more
// elements in the sequence, and moves it forward to the next
// element when there are.
//
// * current(), which returns the current element, and should only be
// called after next() has returned true at least once.

function logFive(sequence) {
for (var i = 0; i < 5; i++) {
if (!sequence.next())
break;
console.log(sequence.current());
}
}

function ArraySeq(array) {
this.pos = -1;
this.array = array;
}
ArraySeq.prototype.next = function() {
if (this.pos >= this.array.length-1)
return false;
this.pos++;
return true;
};
ArraySeq.prototype.current = function() {
return this.array[this.pos];
};

function RangeSeq(from, to) {
this.pos = from - 1;
this.to = to;
}
RangeSeq.prototype.next = function() {
if (this.pos >= this.to)
return false;
this.pos++;
return true;
};
RangeSeq.prototype.current = function() {
return this.pos;
};

logFive(new ArraySeq([1, 2]));
// → 1
// → 2
logFive(new RangeSeq(100, 1000));
// → 100
// → 101
// → 102
// → 103
// → 104

// This alternative approach represents the empty sequence as null,
// and gives non-empty sequences two methods:
//
// * head() returns the element at the start of the sequence.
//
// * rest() returns the rest of the sequence, or null if there are no
// elemements left.
//
// Because a JavaScript constructor can not return null, we add a make
// function to constructors of this type of sequence, which constructs
// a sequence, or returns null if the resulting sequence would be
// empty.

function logFive2(sequence) {
for (var i = 0; i < 5 && sequence != null; i++) {
console.log(sequence.head());
sequence = sequence.rest();
}
}

function ArraySeq2(array, offset) {
this.array = array;
this.offset = offset;
}
ArraySeq2.prototype.rest = function() {
return ArraySeq2.make(this.array, this.offset + 1);
};
ArraySeq2.prototype.head = function() {
return this.array[this.offset];
};
ArraySeq2.make = function(array, offset) {
if (offset == null) offset = 0;
if (offset >= array.length)
return null;
else
return new ArraySeq2(array, offset);
};

function RangeSeq2(from, to) {
this.from = from;
this.to = to;
}
RangeSeq2.prototype.rest = function() {
return RangeSeq2.make(this.from + 1, this.to);
};
RangeSeq2.prototype.head = function() {
return this.from;
};
RangeSeq2.make = function(from, to) {
if (from > to)
return null;
else
return new RangeSeq2(from, to);
};

logFive2(ArraySeq2.make([1, 2]));
// → 1
// → 2
logFive2(RangeSeq2.make(100, 1000));
// → 100
// → 101
// → 102
// → 103
// → 104


My questions:


  1. My solution produces exactly the same results as the author's solutions. I tested all three with various test cases. I did utilize the material of the chapter when writing my solution (the chapter talks about OOP techniques in JavaScript, inheritance and such). Given all this, is my solution wrong or not?

  2. Why are his solutions written the way they are written? I mean, is there something wrong with my approach? Not abstract enough? Is it a bad thing that my method accepts arguments? His methods do not require arguments. Are there any drawbacks to my solution comparing to his? (I must confess, I barely understood the problem, so my solution probably reflects the level of my understanding of the problem.)



Thank you!

Answer

Your solution is not correct, because the whole point of the iterator protocol is to iterate lazily, so that RangeSeq(1, 10000000) doesn't fill up memory with all elements if we only need five.

The author's code is ok, but unnecessarily verbose. Iterator protocols are usually implemented like this:

  • an Iterable is an object that has the iterator() method
  • Iterable.iterator() returns an Iterator object
  • Iterator provides the method .next which returns a pair (done, value). Alternatively, .next can throw an exception when called on an exhausted Iterator.

Examples:

function RangeSeq(from, to) {
    this.iterator = function() {
        var i = from;
        return {
            next: function() { return [i < to, i++] }
        }
    }
}

function ArraySeq(ary) {
    this.iterator = function() {
        var i = 0;
        return {
            next: function() { return [ i < ary.length, ary[i++]] }
        }
    }
}

function logN(seq, n) {
    var it = seq.iterator();

    while (n--) {
        var cur = it.next();
        if (!cur[0]) break;
        console.log(cur[1])
    }
}

logN(new RangeSeq(100, 100000000), 5);

console.log('--------------');

logN(new ArraySeq([11,22,33,44,55,66,77,88,99]), 5);

That said, modern JS engines have this kind of stuff built-in, so the Range example can be written much simpler as

function RangeSeq(from, to) {
    this[Symbol.iterator] = function*() {
        for (let i = from; i < to; i++)
            yield i;
        }
}

n = 0;
rs = new RangeSeq(100, 10000000);

for (let x of rs) {

    if (n++ >= 5) break;
    console.log(x)

}

Comments