Adventures in Stream Composition
Introduction
Streams are one of the closest things to infinity we have in programming. Streams can be thought of as potentially infinite lists that lazily produce data via a function like next() or reduce(). Streams are fantastic for a multitude of reasons, but are not all that practical without the common Stream functions. I really can’t imagine using Streams without my map and filter functions.
It is surprisingly easy to understand most Stream functions once you understand reduce because you can implement them all in terms of a reducer. For example, map can be implemented as in terms of reduce like so:
But things get more interesting when you start looking at the Stream *composition functions like concatenate and zip. These functions make it a lot easier to combine Streams. In addition to these existing functions, I am currently working on a product function for Streams (more on that later). All of these operations are pretty intuitive when you are working with finite lists, but become a bit problematic when dealing with potentially infinite lists.
To better understand the problem, let look at concatenation. Concatenating two lists is trivial. Two arrays can be copied into a new, larger array. Two linked lists can be concatenated by pointing the last element of one to the first element of the other. But how do you concat two Streams? If the first Stream is potentially infinite, you can never reach the second Stream.
[0,1,2,3,4] + [5,6,7,8,9]makes some level of intuitive sense.[1,2,3 ...] + [1,2,3 ...]doesn't make much intuitive sense.
A Small Infinity
When dealing with infinite lists we are not completely on our own. There is another field that has been dealing with these problems a lot longer than us programmers. Mathematics.
We are quite lucky, Streams are the “smallest” infinity, the countable infinity: Aleph-naught. If you would like a short introduction to these terms I would recommend this Vsause video that touches on most of the concepts in this post.
The main take away from the video is cardinality. Streams have the same cardinality as the natural numbers. This means that Streams are a countable infinity, and if we use a pairing function we can prove the product of two Streams is also countable.
Since we can mathematically prove that the product of two Streams is countable, it’s not a question of “if” we can write these Stream composition functions, but “how.”
Concat, Zip, and The Grand Hotel
Hilbert’s Grand Hotel is a wonderful thought experiment that can help us better understand how we can compose Streams.
Hilbert’s Grand Hotel is a thought experiment in which we imagine a hotel with infinite occupied rooms. A guest walks up to the front desk asking for a room. Can we find one for them?
We absolutely can!
If we had a finite number of occupied rooms, the problem is easy. We give the new guest room number N + 1 where N is the number occupied rooms. If there are 10 occupied rooms, we give the new guest the 11th room. But this approach doesn’t work with infinite occupied rooms. We can’t count to room **number ∞ + 1, so there is no function that could ever describe this.
But we can write a function that puts the new guest in the 1st room and move everyone else over one room. With this technique we can actually give the new guest a room.
But what does this mean in programming terms? It means that we can’t properly add elements to the end of a Stream, but we can add them to the beginning. Concatenating elements to the end of an infinite Stream doesn’t work, but concatenate elements to the beginning of the Stream does work. (This is a lot like a Stack, this will be important later when we get to Cartesian Products)
The function
concat :: (FiniteEnumerable, Stream) -> Streamis pretty easy to create. But what aboutconcat :: (Stream, Stream) -> Stream?
The function Stream.concat :: (Stream, Stream) -> Stream actually exists in a lot of languages. This function is sometimes valid. If the first Stream passed is finite, then it will work exactly as expected. But if the first Stream is actually infinite, than the second Stream can never be counted too. In short, Stream.concat does absolutely nothing if the first Stream is infinite.
We can’t strictly concatenate two Streams. But we can still combine them in other ways. To understand how, we revisit Hilbert’s Grand Hotel. If a carriage full of an infinite number of new guests arrives, how does the Hotel accommodate them? They take every guest and move them to double their room number. 1 -> 2, 2 -> 4 such that every odd numbered room is now not occupied. Then, they allow all the new guests to take all the odd numbered rooms.
Instead of concatenating one stream to the end of another, you can cycle between the two. For example: cycle([1..∞], [-1..-∞]) would produce [1,-1,2,-2,3,-3 …] by cycling between the two streams.
Most Stream libraries don’t have a cycle() function like this. Even if they do, it often does something quite different. But many do have a function called zip that does nearly the same thing. Instead of producing every element in a cycle sequentially, zip groups every element of the same cycle. For example: zip([1..∞], [-1..-∞]) would produce [{1,-1},{2,-2},{3,-3} …].
This is wonderful. We now have a clear way to create concat and zip functions. If you are relatively new to Streams, this may have been very interesting. But if you know Streams quite well, you likely have been using zip to compose multiple Streams for a long time. For those people, here is the more interesting part: Stream.product.
Stream.product
In the world of Software we use Cartesian products all the time. Every nested loop in essentially the Cartesian product of the inner and outer loop. But simple nested loops don’t always play well with Streams.
All of these examples create a new stream of tuples {i,j} outputting something like [{1,1},{1,2},{1,3},{1,4} ...]. Unfortunately only j ever increments. This is essentially the same problem as trying to concatenate two Streams. The examples can be thought of as nested loops. If the inner loop is infinite, the outer loop will never increment.
Oddly enough I haven’t seen any major Stream libraries with a function that deals with this problem. I decided to write one for myself: Stream.product. In short, Stream.product will lazily produce every permutation of two Streams. With it, you can make some pretty awesome Streams :)
The Cantor Pairing Function.
The exact implementation Stream.product is a topic for another post, but the general idea is very close to Cantor’s pairing function. In short, the pairing function defines a way to count the product of two infinite lists.

If you lay out the Cartesian product out in a grid and draw the counting order, it is actually pretty intuitive. Just iterate diagonal to the origin. With this function, the product of two countable sets will always be countable. Suddenly you can create the product of two Streams and have it still be countable!
Unfortunately we can’t just copy and paste Cantor’s pairing function to createStream.product. We will need to transform an existing pairing function into something that works well with Streams.
The main issues we have to overcome are:
- Pairing functions don’t have the associative property. IE:
product(product(a,b), c) != product(a,b c) - When dealing with Streams, arrays and indexes have major performance issues.
- Making a pairing function that can take any number of arguments means we need an N dimensional pairing function.
So what do we do? Make a new function that is faster, and built for Streams!
We will take a look at how this works in part 2 (coming soon)
*In this post I use the term composition in the general English sense of creating something new from smaller parts. I am not referring to any specific programming term like Function composition or Object composition. I am sorry if this is confusing to anyone :(
** From my understanding
∞ + 1is not actually the best way to describe a value that comes after an infinite set. The correct way would be to use the ordinal numberω + 1. Unfortunately, most people are not familiar with ordinal numbers. If you are though, I meantω + 1.
