Lazy and infinite data structures

Most of the times, we face problems where the solutions can be expressed as simple IO functions. Given an input the answer to the problem can be determined by following a step by step algorithm.

There are cases though, that there are multiple answers to our problem, or the solutions' space is just not finite (or seem to not be finite). Sometimes, even if the solution can be found operating on finite sets, is more elegant to write our algorithm by imagining that we operate in the infinite space of possible solutions.

What I mean by "a more elegant way" is that many times, is more readable to express the control flow of an algorithm with high level abstractions instead of low level primitives.

The problem is that high level abstractions have their own cost, and certain limitations. For example in Javascript map creates a new intermediate array every time it is chained, and it requires to know the size of the iterable in advance.

Saying that we can be more elegant operating on the infinite space, may sound weird but in reality we do it all the time in our daily life. As long as an infinite construction is finitely describable, we can easily reason about it. Examples of these kind of constructions are:

• Sets of strings over some alphabet
• The set of all positive integers
• Functions that map items between sets

Imagine that we have a list of 100000 integers [1,2,3,4,5,6, ... 100000] and we want to find the first 2 of them that satisfy a certain expression (and the calculation of that expression is time consuming). We could write that in a functional style

There are a few problems in this approach:

• We calculate the result of heavyCalculation even if we don't need it, e.g. if 1,2 already satisfy our requirements.
• Every chain, has to re-iteratare the whole array.
• As mentioned, in JS specifically every time you use .map a new intermedidate array is created, wasting memory.
• We need to know or construct the array beforehand.

Let's see how we can define a data structure, that express the infinite space of positive integers, avoid calculating the whole space of possible solutions and avoid wasting memory (by not creating intermediate iterables).

First lets define a data structure that represents all the positive integers:

Implementing the Symbol.iterator and next let us conform with the iterator protocol and do things like:

Although we can use for ... of we cannot use .map since PositiveIntegers do not support it. Let's define another high abstraction, an interface that express the mapping operation over the infinite space.

It accepts an iterable and loop forever on it calling a callback. Then we can define the map function of PositiveIntegers in terms of InfiniteMap.

This let us do things like:

We are now able to overcome the limitations of the native .map and travel over an infinite set. Let's see how we travel over the infite and stop when we find the "solution" we are looking for.

And use it in our main data structure:

This let us do things like:

There is a problem though. We cannot chain the functions of PositiveIntegers

We can't do:

or

Since map returns InfiniteMap which does not implement the takeUntil, and takeUntil returns InfiniteUntil which does not implement map.

We can fix that by using our PositiveIntegers as base and extend.

We define our InfiniteMap and InfiniteUntil by extending PositiveIntegers. Inside PositiveIntegers we define map and takeUntil using InfiniteMap and InfiniteUntil.

Putting everything together:

And now we can chain our map and takeUntil functions

We don't have to always pass a callback, we can define take that stops after specific number of steps.

This essentially means that

is equal to

We can also defined the each to abstract the for .. of loop.

So we can write

We created a new data structure that express the infinite set of all positive integers. What if we want to express another infinite set, e.g. the Fibonacci Set, or the set of Negative Even Numbers, and we want to use the same functions we defined for the PositiveIntegers ?

We can create a new interface that supports the ability to operate on infinity sets. Let's call it InfinitySupport

Then we can define our sets in relation to that:

And use the functions we defined in the InfinitySupport

So what did we achieved?

• We raised the level of abstraction, by chaining high order concepts.
• We avoid storing intermediate representations, and hence waisting memory.
• We don't operate on the whole set, but we are lazily evaluate on step at a time.

Laziness

In the previous examples, we defer the calculation of a value (the execution of our callback), until we need it. Lazy evaluation usually is combined with memoization. After a value is computed the result is stored in a cache, the next time the calculation is requested, the function returns the stored value instead of computing it again.

We can implement a LazyArray data structure, that supports .map in a lazy way, and avoids re-calculation using memoization.

Inside our LazyMap we use a cache to ensure that the callback doesn't run for the same input more than once.

For example executing the following:

Gives us

The callback function has been invoked only once per uniq input value.

Problems that can be expressed more elegantly

Imagine that we have to implement the game of chess. The possible games are not infinite:

... but probably if we had to model that, would be easier to imagine that they are.

Problems that can be expressed as decision trees are also good candidates for the use of infinite data structures, specially when the nodes of the tree cannot be determined beforehand but we build the tree as we go.

For example if we had a problem that can be expressed as decision tree and we know that each node can have maximum 3 leaves.

We can create a lazy data structure that would allow us to model that:

For example this tree:

could be written like:

Summary

There are certain problems that can be easier model if we imagine that we operate on the infinite space, (even if we don't). Examples:

• Read line by line from a file where we don't know then number of lines
• Streams of data in a message bus
• Problems that can be expressed as decision trees
• Problems that involve permutations or combinations of finite sets

And others that by definition we have to model infinite sets. Being able to model that in high order abstractions, gives us the power to write cleaner and more performant programs (using lazy evaluation and memoization techniques).