Intro to the stream data structure in JS

streams.js

const assert = require("assert");

// Utilities for building and using linked lists
const cons = (a, b) => [a, b];
const car = ([a, b]) => a;
const cdr = ([a, b]) => b;
function toArray(ls, acc = []) {
  if (ls.length === 0) {
    return acc;
  }
  return toArray(cdr(ls), acc.concat([car(ls)]));
}

// First returns a linked-list of the first n elements of a streams
function first(stream, n) {
  if (n <= 0) {
    return [];
  } else {
    const pair = stream();
    return cons(car(pair), first(cdr(pair), n - 1));
  }
}

/**
 * A stream stores an infinite sequence of data.
 *
 * A stream is a function.
 *
 * That function returns two things
 * 1. A value
 * 2. A stream
 */
function nums(i = 0) {
  return cons(i, () => nums(i + 1));
}

assert.deepEqual(toArray(first(nums, 1)), [0]);
assert.deepEqual(toArray(first(nums, 5)), [0, 1, 2, 3, 4]);
assert.deepEqual(toArray(first(nums, -1)), []);

/**
 * Double takes in a stream and returns a stream,
 * where each value in the stream is doubled.
 */
function double(stream) {
  // So it has to return a function...
  return () => {
    const pair = stream();
    // That returns two items
    return cons(
      // 1. A value
      2 * car(pair),

      // 2. A stream
      double(cdr(pair))
    );
  };
}

assert.deepEqual(toArray(first(double(nums), 1)), [0]);
assert.deepEqual(toArray(first(double(nums), 5)), [0, 2, 4, 6, 8]);
assert.deepEqual(toArray(first(double(nums), -1)), []);

/**
 * Accum takes a stream and returns a new stream of the
 * original's running total
 */
function accum(stream, total = 0) {
  return () => {
    const pair = stream();
    total += car(pair);
    return cons(total, accum(cdr(pair), total));
  };
}

/**
 * We can build a stream of the "triangle numbers" by
 * accumulating the `nums` stream.
 */
const triangle = accum(nums);

assert.deepEqual(toArray(first(triangle, 1)), [0]);
assert.deepEqual(toArray(first(triangle, 8)), [0, 1, 3, 6, 10, 15, 21, 28]);
assert.deepEqual(toArray(first(triangle, -1)), []);