comparing different iteration protocols

cat.js

// EXAMPLE: a compound iterator with sequencing

// Python style
function cat() {
    let is = arguments;
    return {
        next: {
            let length;
            while ((length = is.length) > 0) {
                try {
                    return is[length - 1].next();
                } catch (e) {
                    if (isStopIteration(e)) {
                        is.pop();
                        continue;
                    }
                    throw e;
                }
            }
            throw StopIteration;
        }
    };
}

// Java style
function cat() {
    let is = arguments;
    return {
        hasNext: function() {
            let length = is.length;
            return length > 0 && is[length - 1].hasNext();
        },
        next: function() {
            let length;
            while ((length = is.length) > 0) {
                let i = is[length - 1];
                if (!i.hasNext()) {
                    is.pop();
                    continue;
                }
                return i.next();
            }
        }
    };
}

// C# style
function cat() {
    // TODO...
}

// Functional style
function cat() {
    let is = arguments;
    return {
        next: function() {
            let length;
            while ((length = is.length) > 0) {
                let next = is[length - 1].next();
                if (!next) {
                    is.pop();
                    continue;
                }
                return next;
            }
            return null;
        }
    };
}

// Two-callback style
function cat() {
    let is = arguments;
    return {
        next: function(next, done) {
            let length;
            while ((length = is.length) > 0) {
                let next = is[length - 1].next(function(x) {
                    return { value: x };
                }, function() {
                    return null;
                });
                if (!next) {
                    is.pop();
                    continue;
                }
                return next.value;
            }
            return done();
        }
    };
}

// Node-callback style
function cat() {
    let is = arguments;
    return {
        next: function(cb) {
            let length;
            while ((length = is.length) > 0) {
                let next = is[length - 1].next(function(done, x) {
                    return done ? null : { value: x };
                });
                if (!next) {
                    is.pop();
                    continue;
                }
                return next.value;
            }
            return done();
        }
    };
}

range.js

// EXAMPLE: a leaf iterator

// Python style
function range(low, high) {
    let i = low;
    return {
        next: function() {
            if (i >= high)
                throw StopIteration;
            return i++;
        }
    };
}

// Java style
function range(low, high) {
    let i = low;
    return {
        hasNext: function() {
            return i < high;
        },
        next: function() {
            if (i >= high)
                throw new Error("no next");
            return i++;
        }
    };
}

// C# style
function range(low, high) {
    let i = low - 1;
    return {
        get current() {
            if (i < low)
                throw new Error("not started");
            if (i >= high)
                throw new Error("finished");
            return i;
        },
        moveNext: function() {
            i++;
            return i < high;
        }
    };
}

// Functional style
function range(low, high) {
    let i = low;
    return {
        next: function() {
            return i >= high ? null : { value: i++ };
        }
    };
}

// Two-callback style
function range(low, high) {
    let i = low;
    return {
        next: function(next, done) {
            return i >= high ? done() : next(i++);
        }
    };
}

// Node-callback style
function range(low, high) {
    let i = low;
    return {
        next: function(cb) {
            return i >= high ? cb(true) : cb(false, i++);
        }
    };
}

zip.js

// EXAMPLE: a compound iterator

// Python style
function zip(i1, i2) {
    return {
        next: function() {
            return [x1.next(), x2.next()];
        }
    };
}

// Java style
function zip(i1, i2) {
    return {
        hasNext: function() {
            return x1.hasNext() && x2.hasNext();
        },
        next: function() {
            return [x1.next(), x2.next()];
        }
    };
}

// C# style
function zip(i1, i2) {
    return {
        get current() {
            return [i1.current, i2.current];
        },
        moveNext: function() {
            return i1.moveNext() && i2.moveNext();
        }
    };
}

// Functional style
function zip(i1, i2) {
    return {
        next: function() {
            let x1 = i1.next();
            if (!x1)
                return null;
            let x2 = i2.next();
            if (!x2)
                return null;
            return { value: [x1, x2] };
        }
    }
}

// Two-callback style
function zip(i1, i2) {
    return {
        next: function(next, done) {
            return i1.next(function(x1) {
                return i2.next(function(x2) {
                    return [x1, x2];
                }, done);
            }, done);
        }
    };
}

// Node-callback style
function zip(i1, i2) {
    return {
        next: function(cb) {
            return i1.next(function(done, x1) {
                if (done) {
                    return cb(true);
                }
                return i2.next(function(done, x2) {
                    if (done) {
                        return cb(true);
                    }
                    return cb(false, [x1, x2]);
                });
            });
        }
    };
}

zipExtend.js

// EXAMPLE: a compound iterator that checks for end of iteration

// Python style
function zipExtend(i1, i2, extendWith) {
    function next(i, ifDone) {
        try {
            return i.next();
        } catch (e) {
            if (isStopIteration(e)) {
                ifDone();
                return extendWith;
            }
            throw e;
        }
    }

    return {
        next: function() {
            let x1 = done1 ? extendWith : next(i1, function() {
                done1 = true;
            });
            let x2 = done2 ? extendWith : next(i2, function() {
                done2 = true;
            });
            if (done1 && done2)
                throw StopIteration;
            return [x1, x2];
        }
    };
}

// Java style
function zipExtend(i1, i2, extendWith) {
    return {
        hasNext: function() {
            return i1.hasNext() || i2.hasNext();
        },
        next: function() {
            if (!i1.hasNext() && !i2.hasNext())
                throw new Error("end of iterator");
            return [i1.hasNext() ? i1.next() : extendWith,
                    i2.hasNext() ? i2.next() : extendWith];
        }
    };
}

// C# style
function zipExtend(i1, i2, extendWith) {
    // TODO
}

// Functional style
function zipExtend(i1, i2, extendWith) {
    return {
        next: function() {
            var x1 = i1.next(), x2 = i2.next();
            return (!x1 && !x2) ? null : {
                value: [x1 ? x1.value : extendWith,
                        x2 ? x2.value : extendWith]
            };
        }
    };
}

// Two-callback style
function zipExtend(i1, i2, extendWith) {
    return {
        next: function(next, done) {
            return i1.next(function(x1) {
                return i2.next(function(x2) {
                    return next([x1, x2]);
                }, function() {
                    return next([x1, extendWith]);
                });
            }, function() {
                return i2.next(function(x2) {
                    return next([extendWith, x2]);
                }, done);
            });
        }
    };
}

// Node-callback style
function zipExtend(i1, i2, extendWith) {
    return {
        next: function(cb) {
            return i1.next(function(done, x1) {
                return done
                     ? i2.next(function(done, x2) {
                         return done ? cb(true) : cb(false, [extendWith, x2]);
                     })
                     : i2.next(function(done, x2) {
                         return cb(false, [x1, done ? extendWith : x2]);
                     });
            });
        }
    };
}

Looks great and looks very similar to what I have with IxJS:

• L2O
• IxJS

Hopefully most iterators have lots of clients. So comparing the client code could also be instructive as it should carry more weight in making choices.

@johnjbarton Client code almost always looks the same: a for-of loop. The kind of client code that doesn't use a for-of loop is going to be an abstraction that wraps an iterator, like zip and cat. Notice how even though they produce iterators, they are also clients of iterators.

@johnjbarton Because many of these examples are functions that take iterators as arguments and consume those iterators, they do show client code. Look for places where they call .next(), for example.

Won't generators change the landscape a lot here?

I quite like the simplicity of the functional style.

@gf3, yes but it comes at the cost of not being able to iterate over collections containing falsy values. Right?

@allenwb No, the next() method in that style returns either {value: the next value} or null to indicate "no more values".

@skinner Yes, where possible I would always use generators (to produce iterators) and for-of loops (to consume them), but zip() for example can't be done using just for-of loops.

@dherman Do you want to try making zip() handle any number of iterable arguments? It's enough to make me not want either callback style. Callback style + side effects = WAT. Not that you need side effects there... if you have proper tail calls...

With a generator you could change zip into a for...of loop where the second source iterator is manually iterated using .next(). Perhaps a little cleaner?

@allenwb What @jorendorff said. :)

@gf3 Me too :)

@jorendorff I'm going to create a whole repo, since this is getting big enough.

@Benvie Worth a try! Maybe it'll be good to show several alternative implementations side by side.

function zip(i1, i2){
  return (function*(){
    for (item of i1) {
      yield [item, i2.next()];
    }
  })();
}

I think this is the correct syntax for a generator expression? I don't recall if the order got flipped or not.

function zip(i1, i2){
  return (for (item of i1) [item, i2.next()]);
}

@dherman Won't a client of the Python style require a try/catch as illustrated in the zipExtend example?

@Benvie You'd have to iterate on the smaller of the two collections.

FWIW, this is my arbitrary-number-of-arguments zip(), in mozilla's JS with StopIteration:

https://github.com/skinner/munj/blob/ca83c2c315815c0749a32c10af2ea23cdafa241d/munj.js#L389

Not the prettiest, but the best I've been able to think of so far.

@johnjbarton No, certainly not! You just use for-of normally. The exception is completely abstracted away when you use for-of.

New repo with lots of examples. More work to do, feel free to submit implementations via pull request.

https://github.com/dherman/iteration-protocols

N-ary zip

function zip(firstIter, ...iters){
  return (function*(){
    for (let item of firstIter) {
      const items = [item];
      for (let iter of iters) {
        items.push(iter.next());
      }
      yield items;
    }
  })();
}

@gf3 you don't need to. If the first one is shorter, the generator will automatically throw StopIteration at the end. If the second is shorter, then calling its .next() will cause the error to propagate out. This is a benefit to the StopIteration method that isn't as cleanly done with any other iteration protocol.

@Benvie Cool. I think this technique doesn't work for zipExtend, though, because you don't want the first StopIteration to short-circuit others that may not be completed yet.

@Benvie You're assuming that this is the behavior you want and not an accident. I could easily extrapolate the same lessons to zipExtend and have a hidden bug. If I'm forced to do a hasNext or moveNext check, I'm forced to make that choice explicit.

Indeed, it does not universally work. Any time you need to catch StopIterations then the code suddenly becomes a lot more ugly. But it seemed to me to be an intended synergy between generators and iterators and not something that hides bugs.

@Benvie: intended synergy is intended. http://www.python.org/dev/peps/pep-0380/ is worth a read if you haven't.

/be

If I got things right in my ES6 toy implementation, the following generator functions should work:

function* cat(...gs) {
  for (let g of gs) yield* g;
}

function* zip(...gs) {
  while (gs.length) yield gs.map(g => g.next());
}

function* zipExtend(...args) {
  let extendWith = args.pop(), active = 0;
  let gs = args.map(g => cat(g, function*() {
    active += 1;
    while (active != args.length) yield extendWith;
  }()));
  yield* zip(...gs);
}

That is extravagant.