Home

# Operating on Infinite Lists

Today weāre going to step through one of my favorite exercises in composing functions - building and operating on infinite streams of data.
The question weāll be answering is: How might you represent the following operations?
nums
// =>  1, 2, 3, 4, ...
double(nums)
// =>  2, 4, 6, 8, ...
fib
// =>  0, 1, 1, 2, 3, 5, 8, ...
This post contains code written in JavaScript, but the ideas here apply to any language with functions and lists.

## The Finite

We can build a finite list in JavaScript like so:
const ls = [1, 2, 3, 4, 5]
// => [1, 2, 3, 4, 5]
We can access any element inside of it as well as its length:
ls[0]
// => 1
ls[10]
// => undefined
ls.length
// => 5
Alternatively, we can self-referentially represent lists as an element, followed by a list. This is commonly referred to as a ālinked list.ā (Youāre welcome to scroll to the next section if this is familiar to you. Youāre welcome either way I guess, Iām not a cop.)
In this data structure weāll use an object with a first field for the element and a rest field for the rest of the list. Weāll use null for the empty list - where our list ends.
const ll = {
first: 0,
rest: {
first: 1,
rest: {
first: 2,
rest: null,
},
},
}
This is conceptually simpler, but pretty awkward (imagine if you had to use this instead of [...]!). Still, we can access elements inside of it:
ll.first
// => 0
ll.rest.first
// => 1
ll.rest.rest.first
// => 2
And we can compute its length using recursion (where our function is defined in terms of itself):
function length(ll) {
if (ll === null) {
// empty list has length 0
return 0
} else {
// its length is 1 (the item)
// plus the length of the rest
return 1 + length(ll.rest)
}
}
length(ll)
// => 3

## The Infinite

Conceptually, an infinite list is a lot like a finite list. Weāll want a way to get an item, and a way to get the rest. Letās kick things off by building a stream of ones:
1, 1, 1, 1, ...
Our first will be a single piece of data in our stream - in this case, the number 1.
const ones = {
first: 1,
rest: ???,
}
In our linked list above, our rest was also a linked list. Similarly, the rest of our stream will beā¦ a stream!
const ones = {
first: 1,
rest: ones,
}
Youāll quickly find however, that we canāt just define a variable in terms of itself. In JavaScript, weāll receive the following from our console:
ReferenceError: ones is not defined
What can we define in terms of itself? Functions! Remember length from above?
function length(ll) {
if (ll === null) {
return 0
} else {
return 1 + length(ll.rest)
}
}
Soā¦letās switch ones to be a function:
function ones() {
return {
first: 1,
rest: ones(),
}
}
But, weāre not in the clear just yet:
> ones()
RangeError: Maximum call stack size exceeded
at ones (repl:1:14)
at ones (repl:4:11)
at ones (repl:4:11)
Uh oh. When creating our stream, ones is eagerly making subsequent calls to itself over and over again - never coming up for air before our JavaScript console lets us know we probably messed up.
Instead, letās make our implementation lazier by returning the ones function and calling it when we need it.
function ones() {
return {
first: 1,
rest: ones,
}
}

ones()
// => { first: 1, rest: [Function: ones] }
No infinite loops! We can create a ones stream, and gather elements from it like so:
ones().first
// => 1
ones().rest().first
// => 1
ones()
.rest()
.rest().first
// => 1

## Defining and Building Streams

Taking a step back, we can define a stream as a function which returns two things:
1. an item
2. a stream
We can define a twos stream similarly to our ones:
function twos() {
return {
first: 2,
rest: twos,
}
}

twos().first
// => 2
twos().rest().first
// => 2
twos()
.rest()
.rest().first
// => 2
Still, these streams donāt seem particularly useful. One potential smell is our streams are functions, but so far they havenāt taken any arguments. What if they did?
Letās kick things off with a stream of the natural numbers.
function nums(n) {
return {
first: n,
// Remember, rest is a stream,
// and streams are functions.
rest: () => nums(n + 1),
}
}

nums(1).first
// => 1
nums(1).rest().first
// => 2
nums(1)
.rest()
.rest().first
// => 3
nums(999).first
// => 999
An initial argument for nums doesnāt seem particuarly useful, so letās use a default.
function nums(n = 1) {
return {
first: n,
// Remember, rest is a stream,
// and streams are functions.
rest: () => nums(n + 1),
}
}

nums().first
// => 1
All these .rest()/.first chains are becoming cumbersome, so letās take a second and define a function to grab the first n elements of a stream.
function take(stream, n) {
if (n <= 0) {
return []
} else {
const { first, rest } = stream()
return [first].concat(take(rest, n - 1))
}
}

take(nums, 5)
// => [1, 2, 3, 4, 5]
Exercise: Write a function to grab the nth item of a stream
nth(nums, 100)
// => 101
Solution
function nth(stream, n) {
if (n < 0) return null

const {first, rest} = stream()
if (n === 0) {
return first
} else {
return nth(rest, n - 1)
}
}
At this point we have a stream with some interesting data in it.
Now itās your turn. Try the following examples on your own machine. The solutions can be expanded if you get stuck (and itās okay if you do!)
Define a stream which returns the odd numbers.
take(odds, 5)
// => [1, 3, 5, 7, 9]
Solution
function odds(n = 0) {
return {
first: 2 * n + 1,
rest: () => odds(n + 1),
}
}
Define a stream which returns the square numbers.
take(squares, 5)
// => [1, 4, 9, 16, 25]
Solution
function squares(n = 1) {
return {
first: n * n,
rest: () => squares(n + 1),
}
}
Define a stream which loops between 0 and 1.
take(flipFlop, 5)
// => [0, 1, 0, 1, 0]
Solution
function flipFlop(n = 0) {
return {
first: n % 2,
rest: () => flipFlop(n + 1),
}
}
Right on. Feel free to take a break, refill your water, and weāll continue onto the next section - writing functions to operate on our streams.

## Streams Out / Streams In

Now that weāre comfortable creating streams, letās start writing functions that can create streams for us.
To kick things off, letās write a function that takes in a number and returns a stream of that number.
function fixed(n) {
// Streams are functions
return () => ({
// Which return an item...
first: n,

// ...and a stream
rest: fixed(n),
})
}

const sevens = fixed(7)
take(sevens, 5)
// => [7, 7, 7, 7, 7]
Our pattern here is a little different than the ones and twos from earlier - in particular weāre returning a function instead of an object with first and rest.
Additionally, our value for rest is a little simpler since fixed(n) returns a function (we donāt need to make a new one inline like before).
For our next example, letās recall our definitions for odds, squares, and flipFlop. Specifically, just the first and rest parts of each.
odds
first: 2 * n + 1,
rest: () => odds(n + 1),

squares
first: n * n,
rest: () => squares(n + 1),

flipFlop
first: n % 2,
rest: () => flipFlop(n + 1),
Interestingly, our three streams share the same rest! And the first is just a function of n.
Letās materialize this some more, by building a function funcStream to generalize our three examples.
function funcStream(f, n = 0) {
return () => ({
first: f(n),
rest: funcStream(f, n + 1),
})
}

take(funcStream(n => 2 * n + 1), 5)
// => [1, 3, 5, 7, 9]
take(funcStream(n => n * n), 5)
// => [0, 1, 4, 9, 16]
take(funcStream(n => n % 2), 5)
// => [0, 1, 0, 1, 0]
Not bad - but we can do better. funcStream still needs to keep track of its own n and update it appropriately, but nums can do that for us. What if our function operated on nums, or any stream for that matter?
We can think of this as a āmapā equivalent for streams. Hereās how we might do it:
function map(f, stream) {
return () => {
const { first, rest } = stream()

return {
first: f(first),
rest: map(f, rest),
}
}
}

take(map(n => 2 * n, nums), 5)
// => [0, 2, 4, 6, 8]
Using this, we can define functions to operate on streams:
const double = stream => map(n => 2 * n, stream)
take(double(nums), 5)
// => [0, 2, 4, 6, 8]
Better yet, these functions can compose.
take(double(double(nums)), 5)
// => [0, 4, 8, 12, 16]
Letās take stock. nums is an infinite stream of numbers, and weāre able to apply a function to it. Under the hood, this function is lazily invoked when we need it - such as when we display the output with take.
But mapping isnāt the only thing we do with finite lists, so it shouldnāt be the only thing we do with streams. What if we wanted to filter a stream?
take(filter(n => n % 3 > 0, nums), 6)
// => [1, 2, 4, 5, 7, 8]
When filtering a stream, weāll grab itās first and rest, then test first. If the test passes (and the function passed into filter returns true), weāll make sure to include that in the stream.
If the test does not pass, weāll just filter the tail and ignore the first. Letās turn this into code:
function filter(f, stream) {
const { first, rest } = stream()
if (f(first)) {
// Streams are functions
return () => ({
first: first,
rest: filter(f, rest),
})
} else {
// Ignore first, filter rest
return filter(f, rest)
}
}
And just like that, we now have a filter that operates on an infinite stream of data.
take(filter(n => n % 2 > 0, nums), 5)
// => [1, 3, 5, 7, 9]
take(filter(_ => true, nums), 5)
// => [0, 1, 2, 3, 4]
take(filter(_ => Math.random() < 0.05, nums), 5)
// => [28, 31, 33, 37, 54]

## Closing Exercises

Before you go, try your hand at the following exercises.
Using map, create a FizzBuzz stream.
take(fizzbuzz, 5)
// => [1, 2, 'Fizz', 4, 'Buzz']
Solution
const fizzbuzz = map(n => {
if (n % 15 === 0) {
return 'FizzBuzz'
} else if (n % 3 === 0) {
return 'Fizz'
} else if (n % 5 === 0) {
return 'Buzz'
} else {
return n
}
}, nums)
Using map and nums, write a function that takes two values and produces a stream that toggles between them.
take(toggle("hi", "ho"), 5)
// => ['hi', 'ho', 'hi', 'ho', 'hi']
Solution
function toggle(a, b) {
return map(
// nums starts at 1
n => (n - 1) % 2 === 0 ? a : b,
nums
)
}
Using map and nums, write a function that takes an array of values and produces a stream that cycles between them.
take(cycle(["a", "b", "c"]), 5)
// => ['a', 'b', 'c', 'a', 'b']
Solution
function cycle(items) {
return map(
// nums starts at 1
n => items[(n - 1) % items.length],
nums
)
}
Write a function that takes two streams and interleaves them.
take(interleave(fixed(0), fixed(9)), 5)
// => [0, 9, 0, 9, 0]
Solution
function interleave(a, b) {
const aPair = a()
const bPair = b()

return () => ({
first: aPair.first,
rest: () => ({
first: bPair.first,
rest: interleave(aPair.rest, bPair.rest),
})
})
}
Write a function which accepts a stream and returns a new stream whose values are a running total of the original stream.
For nums: return 1, then 1 + 2, then 1 + 2 + 3, then 1 + 2 + 3 + 4, etc.
take(total(nums), 6)
// => [1, 3, 6, 10, 15, 21]
Hint: give total a second argument that defaults to 0
Solution
function total(stream, value = 0) {
return () => {
const pair = stream()
return {
first: value + pair.first,
rest: total(pair.rest, value + pair.first),
}
}
}
Write reduce for streams.
reduce should take a 2-argument accumulator function, an initial value, and a stream.
take(reduce((acc, value) => acc + value, 0, nums), 6)
// => [1, 3, 6, 10, 15, 21]
take(reduce((acc, value) => acc * value, 1, nums), 6)
// => [1, 2, 6, 24, 120, 720]
Hint: Generalize your solution for total.
Solution
function reduce(fn, init, stream) {
return () => {
const pair = stream()
const newValue = fn(init, pair.first)
return {
first: newValue,
rest: reduce(fn, newValue, pair.rest),
}
}
}
Using map and reduce, create a stream of the Fibonacci sequence.
take(fib, 8)
// => [0, 1, 1, 2, 3, 5, 8, 13]
Hint #1: Your initial value should be the first two values of the sequence.
Hint #2: You do not need to use the input streamās values.
Solution
function fib() {
return {
// reduce will consume the first
// 0, so we'll manually put it
// at the front
first: 0,
rest: map(
pair => pair[0],
reduce(
([a, b], _) => [b, a + b],
[0, 1],
fixed('foobar')
)
)
}
}
Using nothing but functions and some JavaScript objects, we were able to create and modify infinite sequences of data - and we did it all without making our computer cry!
Thanks for reading this post, and an extra special thanks if you took the time to go through the exercises I put together after lots of editing. I really appreciate it. If not, you may want to try them out on a rainy day, I bet youāll learn something!
It would be a mistake to leave you without some links for further reading.