Recursive Data Structures and Lazy Evaluation
Tags: learning, tutorial, algorithms, functional
Published: 2018-01-07 19:25:22

---
title: Recursive Data Structures and Lazy Evaluation
published: true
description: In this article I’m trying to explain to myself recursive data structures and how they work together with lazy evaluation. I happen to use them everyday, but never really thought about underlying implementation and the idea in general.
tags: learning, tutorial, algorithms, functional
canonical_url: https://romanliutikov.com/blog/2017/07/29/recursive-data-structures.html
cover_image: https://thepracticaldev.s3.amazonaws.com/i/5yy67lunfvssnwbipc6e.jpg
---
_In this article I’m trying to explain to myself recursive data structures and how they work together with lazy evaluation. I happen to use them everyday, but never really thought about underlying implementation and the idea in general._

First we define a problem and describe recursive solution to it. After that we are going to implement a simple data structure, recursively. And once we get the idea, I’ll cover lazy evaluation and present lazy variant of that data structure.

##The Problem

A typical problem in game development is collision detection. This technique is used to detect intersection between entities in coordinate space, such as enemies and bullets in shooter games for example.

![](https://thepracticaldev.s3.amazonaws.com/i/lihb8wtd6akhpwmlssqv.png)

Let’s imagine we are building 2D space shooter game. The game involves interaction between enemy entities and player’s missiles. In order to say if enemy entity is destroyed the game should be able to detect when the missile intersects an entity in two-dimensional coordinate space. In the context of our game collision detection algorithm could be described as the following:

1. Compose a list of all missile entities and a list of all enemy entities currently on the screen
2. Take the first/next missile entity from the list
3. Check it’s position against all enemy entities
    - if position matches — collision is detected, remove both entities from the list and repeat from step 2
    - otherwise — repeat from step 2 until the end of the list

As you can see the algorithm is straightforward and can be easily implemented via iteration.

```js
for (let i = 0; i < missiles.length; i++) {
  const missile = missiles[i];
  for (let j = 0; j < enemies.length; j++) {
    const enemy = enemies[j];
    if (missile.intersects(enemy)) {
      // collision is detected
    }
  }
}
```

The problem however is that this naive approach takes `O(n*(n-1))` or simply `O(n^2)` time to execute, meaning that every time the number of entities doubles the number of iterations required to detect collision between all entities is going to be four times larger. That is for 3 entities it takes roughly 9 iterations, 900 iterations for 30 entities, 90000 for 300 entities and so on. It’s totally fine to use this approach if a single check is relatively cheap operation and there are not much entities on a screen, but sometimes that’s not the case.

##Solution

An obvious improvement would be to perform collision check for a given entity only against entities that are close to it, discarding all distant entities. Screen area can be divided into separate areas to form a grid and now for every entity we can perform collision check only against other entities currently in the same area. This technique is called _space partitioning_.

![](https://thepracticaldev.s3.amazonaws.com/i/edurpjsysojvfissbktu.png)

More sophisticated algorithm would be to use an adaptive grid, where cells can subdivide itself based on how much entities there are currently in a given cell.

###Recursive algorithm

One of the algorithms implementing adaptive grid approach is called _quadtree space partitioning_. A quadtree is a data structure where every node has exactly four child nodes, hence the name. A quadtree is recursive because it is defined in terms of itself (every node, except leaf nodes, has another quadtree as its subtree).

Game canvas can be divided between those nodes where each node would represent an area on the screen defined by its bounds. A node may hold entities that are currently in the area which corresponds to that node. Quadtree nodes should be set a maximum number of entities they can hold (maximum number of entities in a given area). Once capacity of the node is full, the node subdivides itself into four child nodes and spreads its entities across child nodes with respect to their position on the screen. Subdivision can be infinitely deep, but usually the maximum number of levels is set.

The benefit of this approach is that in the best case, when all entities are spread evenly across the screen, the time required to perform all collision checks is reduced by 4x with every level of subdivision. That is, for 100 entities we get 2500 checks instead of 10000 with one level of subdivision, with two levels it is 625 checks and so on. This can reduce CPU load when applied correctly, but don’t forget that maintaining a quadtree also consumes CPU cycles and memory.

<a href="https://jsbin.com/qeqize/edit?js,output">
    <img src="https://thepracticaldev.s3.amazonaws.com/i/weod8vrqldtigb1wwtnj.png" />
</a>

What we’ve just learned is that game development is fun and algorithms are not that hard, but most importantly in this section we’ve seen how recursive data structures could be a natural fit as a solution to a certain type of problems. Now let’s see the code.

##Recursive data structures

In this section we are going to build `List` data structure, singly linked list to be precise. A list is fundamental data structure in functional programming known from early days of Lisp programming language. Take a look at type declaration of List data type in Haskell

```js
data List a = Nil | Cons a (List a)
```

You can see that a list is either `Nil` (empty list) or `Cons` (construction) of a value and another list. Having another list as the next value in a list is what makes this data structure recursive or defined in terms of itself. The last value in a list is always `Nil`, it is used to signal that the end of list is reached. `Nil` is also treated as empty list, which means that this type inherits properties of a list. To get better understanding here’s how a list of three items could be written in pseudo code:

```
[1 [2 [3 nil]]]
```

A tuple of two items here is called a cons (construction) cell. A cons cell consists of a value at the first position (head) and a pointer to another value (tail). Thus a list of three items is essentially a chain of three cons cells with `Nil` in the last cell to indicate the end of list. This can be also visualized as the following:

![](https://thepracticaldev.s3.amazonaws.com/i/ic6kcstv3nir9i64om46.png)

A list built on cons cells has interesting properties such as access to the head of list and its tail in constant time. On the other hand lists doesn’t provide efficient random access such as in indexed collections (arrays).

Now that we know underlying representation of a list, lets create our own implementation. First we define data types — building blocks of a list. They are: `List`, `Cons` and `Nil`. `List` type is not really necessary to build a list, because a list is just a chain of cons cells with `Nil` in the end. It is rather a useful abstraction which could provide us with an API for creating and manipulating lists.

First we implement type `Nil` as JavaScript class and create an instance of the class, a variable named `nil`, to be used as a marker of the end of a list.


```js
class Nil {
  toString() {
    return 'Nil';
  }
}

const nil = new Nil();
```

The next type is `Cons`. It is a class that accepts `head` value and `tail` — a reference to the next value. We also create a helper static method `.of` to avoid using `new` keyword.

```js
class Cons {
  constructor(head, tail = nil) {
    this.head = head;
    this.tail = tail;
  }
  toString() {
    return `Cons(${this.head}, ${this.tail})`;
  }
}

Cons.of = (head, tail) => new Cons(head, tail);
```

Using just cons cells we can already create lists of values and access those values:

```js
const list = Cons.of(1, Cons.of(2, Cons.of(3, nil)));

console.log(list.head);
console.log(list.tail.toString());
console.log(list.tail.head);
console.log(list.tail.tail.tail.toString());
```

As I mentioned before cons cells are enough for creating lists, but list abstraction built on top of `Cons` could save us a little time and code by providing an API to create and manipulate lists. So lets built `List` type on top of `Cons`:

```js
class List extends Cons {
  constructor(head, tail) {
    super(head, tail);
  }
  toString() {
    return `List(${this.first()}, ${this.rest()})`;
  }
  first() {
    return this.head;
  }
  rest() {
    return this.tail;
  }
}

List.of = (head, tail) => new List(head, tail);

List.fromValues = (head, ...tail) => {
  if (tail.length > 0) {
    return List.of(head, List.fromValues(...tail));
  } else {
    return List.of(head, nil);
  }
};
```

We also implement `.fromValues` helper for creating lists from arbitrary number of arguments. Note how it builds a list recursively.

```js
const list = List.fromValues(1, 2, 3);

console.log(list.toString());
```

Another useful operation would be generating a range of values. Add a new static method to `List` class definition:

```js
List.range = (start, end) => {
  if (start < end) {
    return List.of(start, List.range(start + 1, end));
  } else {
    return nil;
  }
};
```

`take` method is used to _take_ an arbitrary number of values from a list.

```js
take(n) {
  if (n > 0) {
    return List.of(this.first(), this.rest().take(n - 1));
  } else {
    return List.of(this.first(), nil);
  }
}
```

Quick test with `range` and `take`

```js
const list = List.range(0, 10);

console.log(list.take(3).toString());
```

So far we’ve implemented only retrieval and list creation operations. Lets also create operations for adding values to list and mapping over its values: `add` and `map` methods.

`add` operation is super cheap, because list supports efficient addition to the head, just create a new list with value in head position and target list in tail position, it is as simple as that:

```js
add(value) {
  return List.of(value, this);
}
```

`map` operation also returns a new list where a value in head position is applied recursively to mapper function:

```js
map(fn) {    
  const first = this.first();
  const rest = this.rest();

  if (rest === nil) {
    return List.of(fn(first), nil);
  } else {
    return List.of(fn(first), rest.map(fn));
  }
}
```

```js
const list = List.range(1, 4).add(0).map(n => n * n);

console.log(list.toString());
```

Operations such as `filter` and `reduce` could be implemented similarly to `map`.

In this section we’ve learnt about `List` data structure and its recursive implementation. Similar reasoning could be applied to build quadtree mentioned earlier and any other data structure as well. Later here we will create lazy version of `List`.

##Lazy and eager evaluation

Before we dive into implementing lazy variant of `List` lets quickly remind ourselves what is lazy evaluation.

There are two evaluation strategies: eager and lazy. In short eager means now or to execute immediately and lazy — later or to delay execution until result is needed. Lazy evaluation is essentially an optimization technique. A real world analogy would be lazy loading images on a web page. When you open a website with a bunch of images the browser will start downloading them all immediately. On the other hand we could save bandwidth by loading only those images that are currently visible in browser window. Non of the images below the fold should load until the page scrolled to a position where they become visible. The same applies to code: a set of operations are executed on demand, when the result is actually needed.

Eager evaluation is more straightforward in a sense that it’s easier to reason about. It’s a standard evaluation strategy in languages like JavaScript and Ruby. Consider the following example (evaluation process is described in comments):

```js
range(0, 10) // [0..9]
  .map(n => n + 1) // [1..10]
  .filter(n => n % 2 === 0) // [2 4 6 8 10]
  .take(3) // [2 4 6]
```

You can see that the code is executed in-place and result returned immediately.

Lazy evaluation strategy is different.

```js
range(0, 10) // nothing happened
  .map(n => n + 1) // nothing happened
  .filter(n => n % 2 === 0) // nothing happened
  .take(3) // nothing happened
  .run() // [2 4 6]
```

Here none of the operations in the chain are executed until the call to `.run` method. `nothing happened` is of course not entirely true. When called each operation is being saved for later execution and when the result is requested the whole chain is executed and the final value is returned. Languages like Haskell and Clojure relies heavily on delayed execution. In Haskell for example everything is stored in thunks. You can think of a thunk as a container for arbitrary code that prevents its evaluation. It could be a closure that contains an expression. Eager version of `1 + 1` can be represented as lazy `() => 1 + 1` in JavaScript. As an example let’s create lazy functions to add and subtract numbers:

```js
const add = (a, b) => {
  return () => {
    a = typeof a === "function" ? a() : a;
    b = typeof b === "function" ? b() : b;
    return a + b;
  };
};

const sub = (a, b) => {
  return () => {
    a = typeof a === "function" ? a() : a;
    b = typeof b === "function" ? b() : b;
    return a - b;
  };
};
```

Both `add` and `sub` returns a function that is closed over the arguments, thus the actual operation is not executed yet, until we force it by calling returned thunk.

```js
const thunk = fn => {
  fn.toString = () => '[Thunk]';
  return fn;
};



const add = (a, b) => {
  return thunk(() => {
    a = typeof a === "function" ? a() : a;
    b = typeof b === "function" ? b() : b;
    return a + b;
  });
};

const sub = (a, b) => {
  return thunk(() => {
    a = typeof a === "function" ? a() : a;
    b = typeof b === "function" ? b() : b;
    return a - b;
  });
};



const result1 = sub(20, add(10, 5));
const result2 = add(3, sub(5, 7));
const result3 = add(result1, result2);

console.log(result1);
console.log(result2);
console.log(result3);

console.log(result3());
```

Lazy evaluation always comes with memoization which is yet another optimization. Once a thunk was evaluated it can cache the result in closure and return cached value on subsequent calls instead of evaluating the whole thing again and again. Here’s modified version of previous example:

```js
const memoize = (fn) => {
  let cache;
  return () => {
    if (cache) {
      console.log('Return cached');
      return cache;
    } else {
      console.log('Evaluate');
      cache = fn();
      return cache;
    }
  };
};



const add = (a, b) => {
  return memoize(() => {
    a = typeof a === "function" ? a() : a;
    b = typeof b === "function" ? b() : b;
    return a + b;
  });
};

const sub = (a, b) => {
  return memoize(() => {
    a = typeof a === "function" ? a() : a;
    b = typeof b === "function" ? b() : b;
    return a - b;
  });
};



const result1 = sub(20, add(10, 5));
const result2 = add(3, sub(5, 7));
const result3 = add(result1, result2);

console.log(result3());
console.log(result3());
```

##Lazy and recursive data structures

Below is the initial implementation of `LazyList` abstraction which we are going to build on top of `Cons` type.

```js
class LazyList {
  constructor(fn) {
    this._fn = fn;
  }
  toString() {
    return `LazyList(${this.next()})`;
  }
  next() {
    return this._fn();
  }
  first() {
    return this.next().head;
  }
  rest() {
    return this.next().tail;
  }
}

LazyList.of = fn => new LazyList(fn);
```

`fn` here is a thunk which should return a cons cell and `next` method evaluates the thunk.

See how `.fromValues` helper builds a list lazily and recursively. It returns an instance of `LazyList` which contains a thunk of `Cons` with `head` as value from arguments and `tail` as another lazy list.

```js
LazyList.fromValues = (head, ...tail) => {
  return LazyList.of(() => {
    if (tail.length > 0) {
      return Cons.of(head, LazyList.fromValues(...tail));
    } else {
      return Cons.of(head, nil);
    }
  });
};
```

```js
const list = LazyList.fromValues(1, 2, 3);

console.log(list.toString());
```

`take` also returns a lazy list. But in order to take actual values it evaluates thunks one by one, taking from the tail of the target list, and constructs a new one.

```js
take(n) {
  if (n > 0) {
    return LazyList.of(() => {
      const head = this.first();
      const tail = this.rest();

      if (tail === nil) {
        return Cons.of(head, nil);
      } else {
        return Cons.of(head, tail.take(n - 1));
      }
    });
  }
}
```

`range` returns a range of values, except that now with laziness it is possible to create infinite lists.

```js
LazyList.range = (start = 0, end = Infinity) => {
  if (start < end) {
    return LazyList.of(() => Cons.of(start, LazyList.range(start + 1, end)));
  }
};
```

```js
const list = LazyList.range();

console.log(list.take(2).toString());
console.log(list.take(5).toString());
```

Adding a value to a lazy list is very similar to `List` implementation

```js
add(value) {
  return LazyList.of(() => Cons.of(value, this));
}
```

`map` operation is also similar to its eager variant

```js
map(fn) {    
  return LazyList.of(() => {
    const first = this.first();
    const rest = this.rest();

    return Cons.of(fn(first), rest.map(fn));
  });
}
```

Now we can create an infinite list of values with a set of operations defined on it.

```js
const list = LazyList.range().map(n => n * n);

console.log(list.take(2).toString());
console.log(list.take(5).toString());
```

So far we had only one method for evaluating entire list: `.toString`. In order to be able to consume a list using common JavaScript facilities it should be converted to something meaningful, for example array. `.toArray` method does exactly this.

```js
toArray() {
  const first = this.first();
  const rest = this.rest();

  if (rest === nil) {
    return [first];
  } else {
    return [first, ...rest.toArray()];
  }
}
```

```js
list.take(5).toArray()
```

Let’s add memoization now. Every time someone calls `.next` method to retrieve a value from a list we either evaluate a thunk and memoize the result or just return the result if it was already cached. Here’s what modifications need to be done to `LazyList` class:

```js
constructor(fn) {
  this._fn = fn;
  this._next = null; // cache
}

next() {
  // if there's a thunk
  if (typeof this._fn === 'function') {
    this._next = this._fn(); // evaluate it and cache the result
    this._fn = null; // we don't need thunk anymore
    return this._next; // return cached  value
  } else {
    // other just return cached value
    return this._next;
  }
}
```

See this example of pulling user records lazily from database. `getUsers` function produces a list of user records lazily by pulling them out of database on demand, when the thunk is evaluated.

```js
const getUsers = (db, [id, ...ids]) => {
  return LazyList.of(() => {
    if (ids.length > 0) {
      return Cons.of(db.getUserByID(id), getUsers(db, ids));
    } else {
      return Cons.of(db.getUserByID(id), nil);
    }
  });
};

// usage
const ids = db.getUsersIDs();
const users = getUsers(db, ids); // nothing happened
const firstThreeUsers = users.take(3).map(({ id }) => id); // nothing happened

firstThreeUsers.toArray(); // [1, 2, 3]
```

Let’s test this. If you run the code below you will see that the first run takes ~1s but the next one takes less than 1ms, even though we execute different operations. This happens because `users` list was evaluated on the first run and result was memoized for subsequent calls.

```js
// benchmark helper
const time = (fn) => {
  const start = performance.now();
  const result = fn();
  const delta = performance.now() - start;
  console.log(Math.round(delta * 100) / 100);
  return result;
};

// db mock
const db = {
  getUsersIDs() {
    return [1, 2, 3, 4, 5, 6];
  },
  getUserByID(id) {
    for (let i = 0; i < 1e8; i++) {}
    return { id };
  }
};

const getUsers = (db, [id, ...ids]) => {
  return LazyList.of(() => {
    if (ids.length > 0) {
      return Cons.of(db.getUserByID(id), getUsers(db, ids));
    } else {
      return Cons.of(db.getUserByID(id), nil);
    }
  });
};

const users = getUsers(db, [1, 2, 3, 4, 5, 6]);

time(() =>
   users
     .take(6)
     .toArray());

time(() =>
  users
    .map(id => 'user id ' + id)
    .take(3)
    .toArray());
```

Thats pretty much it 🎬

If you are interested in learning functional data structures, I highly recommend to read Okasaki’s book [“Purely Functional Data Structures”](https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf).