be-stream v0.0.2-alpha

stream

The One Rule: When defining a stream, the rest of the stream must be wrapped in a function of no arguments.

const ones = Stream.make(1, () => ones);
                         // ^^^^^^^^^^

Basics

The stream is a data structure. It is similar to a linked list. An element of a singly linked list has a datum and a reference to the next element. That next element has a pointer to the element which follows. In one sense each element has a pointer to the next; in another, the pointer is to the "rest" of the list.

Here is where streams differ. Like a linked list, the stream has a datum which represents the "head" of the stream. This is the current value. Instead of a reference to the rest of the list, a stream has instructions for creating the rest of the list.

Here's an example at the node REPL:

const ones = Stream.make(1, () => ones);
// undefined
ones;
// Stream { first: 1, rest: [Getter] }

Stream.make returns a Stream instance. ones refers to this instance. ones.first represents the current value of the sequence. ones.rest is the next object

When thinking about how streams are implemented, I find it helps to see the Stream instance as similar to the node of a list. When manipulating them, it is easier to see the Stream instance as representing the whole sequence of Stream instances that it implies.

Lazy evaluation

The reason that the One Rule must be follow is that otherwise, the "rest" would be immediately evaluated. For infinite streams, computation would never cease.

The One Rule brings lazy evaluation to JavaScript. For a stream, the "first" part is evaluated and ready to be used. The "rest" of the stream is treated as not-yet-ready.

If we didn't wrap the "rest" argument in an arrow function, its content would be immediately evaluated. For infinite streams, like the ones examples, this would result in an infinite loop.

Memoization

function addStreams(a, b) {
  return Stream.map((x, y) => x + y, a, b);
}

const fib = Stream.make(0,
                        () => Stream.make(1,
                                          () => addStreams(fib.rest, fib)));

Here's what matters: fib always refers to the same thing in this definition. We can define fib recursively. That's because the recursive references to fib are in function bodies. These bodies won't be executed until we try to access the rest of fib.

We've defined fib always to refer to the same stream. We aren't making a new fib every time we need to inspect its members. Because of this, we "remember" the elements of fib as we access them. A statement like Stream.ref(fib, 120) evaluates almost instantly.

Reference

Instance

# stream.first

The first property is calculated at construction time. It's the first value in the stream of values represented by the current stream instance.

# stream.rest

The rest property is calculated at selection time. When it is accessed, the function passed to the constructor of the stream is invoked.

The value of rest should be a stream instance, or Stream.emptyStream if the end of the stream has been reached.

Class

Constructor

# Stream(car, cdr)

car and cdr are the arguments from which first and rest will be derived.

cdr must be a function of no arguments.

It can look a bit messy with the new operator in definitions. See the convenience constructors section below for pretty alternatives.

Selectors

# Stream.first(stream) # Stream.rest(stream)

These selectors return properties of a stream instance. They are helpful for passing as functional arguments.

# Stream.emptyStream(stream)

Returns the Symbol for the empty stream. If the rest of a stream turns out to equal this Symbol, the end of the stream has been reached.

# Stream.isEmpty(stream)

return stream === Stream.emptyStream;

# Stream.isStream(stream)

return stream instanceof Stream || stream === Stream.emptyStream;

# Stream.ref(stream, n)

Returns nth (0-indexed) element of stream.

# Stream.length(stream)

Returns the number of elements in stream. If stream is infinite, so is the duration of this function's execution.

Convenience constructors

# Stream.make(car, cdr)

Returns a new instance of Stream without having to use the new keyword.

# Stream.from(iterable)

Creates a stream which will return elements of iterable in order. It does NOT create a copy of the iterable. Therefore, modifying the object passed to from is a Bad Idea.

# Stream.of(...elements)

Creates a stream which will return the arguments passed to it in order. Really, it calls from on the array of arguments it receives. Because there should be no other references to that array of arguments, it's generally safer to use than from.

Conversion

# Stream.toArray(stream)

Returns an array with each element yielded by the stream. If the stream is infinite, this will break.

Sequence methods

Here are the types of operations you would expect to be able to do on any sequence. The case of streams, these become powerful primitives.

# Stream.map(proc, ...streams)

Applies proc to successive elements of streams. These are applied in parallel:

// Returns a Stream whose elements are sums of `a` and `b`
function addStreams(a, b) {
  return Stream.map((x, y) => x + y, a, b);
}

# Stream.filter(pred, stream)

Return a stream whose elements are the elements of stream for which pred returns true when they are passed as arguments.

Stream operations

# Stream.shift(stream, x)

Return a stream whose nth element is the product of x and the nth element of stream.

# Stream.scale(stream, x)

Return a stream whose nth element is the product of x and the nth element of stream.

# Stream.interleave(a, b)

Return a stream whose elements are the union of a and b. The ordering alternates: first a member of a, then a member of b and so on.

Well-known streams

# Stream.integers

0, 1, 2, ...

# Stream.inteval(lo, hi)

lo, lo + 1, ..., hi

# Stream.iota(count, start = 0, step = 1)

start + (step * 0), start + (step * 1), ..., start + (step * count)

# Stream.fibs

1, 1, 2, 3, 5, 8, 13, ...

fibs demonstrates the power of memoization. Even though you can treat this stream as a sequence, its members are calculated as-needed. This calculation is as efficient as an iterative, imperative process. That's because as each element of the stream is produced, its value is remembered. The value of the nth element of fibs is just the sum of the (n-1)th and the (n-2)th, the values of which are both remembered.

Prior art

https://mitpress.mit.edu/sicp/