Real World Reactive Programming – Immutable Data Structures

frp Sep 26, 2019

In the previous article in the ‘Real World Reactive Programming’ series, I talked about how we can use React and Bulb to build reactive web applications in JavaScript.

This article takes these concepts a little further. We'll be looking at immutable data structures and how they can be used to improve both the design and performance of our apps. To illustrate these concepts, we'll be writing a simple game in the reactive style.

The source code for the game is available on GitHub, or you can play the finished version in your browser.

The Memory Game

You’ve most likely played some variant of the Memory card game before. In this game, picture cards are placed face-down on the table and arranged into in a 4x4 grid. The object of the game is to find all of the pairs of cards that have the same picture on them, in the fewest number of guesses.

The player makes a guess by choosing a pair of cards to see whether they match. If they match, then they are removed from the table. Otherwise the cards are turned face-down again on the table, and the player repeats the process. The game is completed when the player correctly guesses all pairs of matching cards.

The Game of Memory
The Game of Memory

Choosing a Data Structure

The first thing to consider when building a game is the data structure – that is, how we represent the internal state of the game. For the game of Memory, we obviously we need to store a list of the cards placed on the table – but we also must keep track of which cards the player has selected, which cards have been removed from the table, and how many guesses the player has made.

When it comes to choosing a data structure, the simple fact is that there is never one right answer. The solution we end up with is going to be a trade off between multiple factors, such as performance, complexity, and maintainability.

As with most things when writing software, it is better to start with something simple and evolve it as we go. If we were to choose a more complex data structure from the outset, then we risk over-engineering things. This might create unnecessary work for ourselves later on down the track.

Bearing all that in mind, for our first attempt we could use something like this:

{
  cards: [
    { 
      id: 1,
      shape: '🐝',
      state: 'normal'
    }, { 
      id: 2,
      shape: '🐡',
      state: 'selected'
    },
    ...
  ],
  guesses: 0
}

This data structure is fairly simple; we have a list of cards and a number of guesses. Each card is represented by an object which has the following properties:

  • id: A unique identifier for the card.
  • shape: The shape of the card (i.e. an emoji character).
  • state: The state of the card (i.e. normal, selected, or removed).

Now that we have a data structure, let’s see how well it holds up when actually building the game.

The Case Against Mutability

Let’s imagine that we want to write a function to handle when the player selects a card with a given id. To update the game state to reflect this change, we will need to find the matching card in the data structure and update it:

function selectCard (id, gameState) {
  const card = gameState.cards.find(card => card.id === id)
  card.state = 'selected'
  return gameState
}

At first glance, this implementation of selectCard seems perfectly reasonable. But within this simple function lies an insidious little detail: we just changed – or mutated – the original data structure.

Much of the JavaScript code you see published in books and blog posts does this sort of thing all the time. What’s so bad about mutation?

The short answer is that it’s not great — it is much more difficult to reason about the behaviour of your program, leads to more complex code, is difficult to test, and can lead to bugs that are hard to track down.

I’m not going to go into a huge amount of detail here, but if you are interested I suggest you do some more reading on functional programming and immutable data structures in JavaScript (or other languages). I highly recommend the book Composing Software by Eric Elliot.

In order to rewrite selectCard as a pure function – so that it has no side effects – we must avoid mutating the original data structure. That means we need to make a copy of the game state before we make any changes to it. Finally, we can return the modified copy:

function selectCard (id, gameState) {
  // Find the index of the card we want to select.
  const index = gameState.cards.findIndex(card => card.id === id)

  // Create a copy of the card, and set the state to selected.
  const card = { ...gameState.cards[index], state: 'selected' }

  // Create a copy of the cards.
  const cards = [...gameState.cards]

  // Splice in the new card.
  cards.splice(index, 1, card)

  // Return a copy of the game state, with the updated cards.
  return { ...gameState, cards }
}

Now that we have written a pure version of our selectCard function, it might be worth revisiting our data structure to judge its efficacy. Are there are any obvious changes we could make in order to simplify things?

Revisiting Our Data Structure

One thing that stands out in particular, is that every time we want to find a card with a given identifier, we have to search through the entire list of cards. This seems horribly inefficient, given that finding a card is something we will need to do quite often in our code. Perhaps using an array to represent the cards wasn’t the best choice?

Instead, we could store the cards as a map from card identifiers to cards. This way, we can find a card with a given identifier much more efficiently (in constant time).

{
  cardsMap: {
    1: { 
      id: 1,
      shape: '🐝',
      state: 'normal'
    },
    2: { 
      id: 2,
      shape: '🐡',
      state: 'selected' 
    },
    ...
  },
  guesses: 0
}

With the updated data structure, our selectCard function now becomes:

function selectCard (id, gameState) {
  // Create a copy of the card object with the state set to selected.
  const card = { ...gameState.cardsMap[id], state: 'selected' }

  // Create a copy of the cards map with the updated card.
  const cardsMap = { ...cardsMap, [id]: card }

  // Return a copy of the game state with the updated cards map.
  return { ...gameState, cardsMap }
}

We can go even further and tidy things up using the wonderful FKit library:

import { set, update } from 'fkit'

function selectCard (id, gameState) {
  // The key path of the property to update.
  const keyPath = ['cardsMap', id]

  // Set the state to 'selected' for the card at the key path.
  return update(keyPath, set('state', 'selected'), gameState)
}

Now we are really getting somewhere. The above example is simple, elegant, and declarative. Our colleagues (and future selves) will appreciate how easily they are able to understand the selectCard function. It couldn’t get any simpler...could it?

import { set, update } from 'fkit'

const selectCard = id => update(['cardsMap', id], set('state', 'selected'))

Now we're just showing off. Using currying (FKit’s functions are automatically curried by default), we are actually able to condense it into a one-liner – but whether that makes the intent more obvious is a matter of personal taste. It's certainly very declarative – focussed on the what, rather than the how.

Libraries like FKit, Ramda, and Lodash can provide you with the syntactic sugar to make working with immutable data structures a breeze, but make sure you understand the fundamentals before you reach for a library.

Using Classes

Up until now, when talking about immutable data structures we haven’t mentioned anything about classes. After all, classes tend to imply encapsulation – the bundling of data and methods that operate that data. But that doesn’t mean we can’t write immutable classes.

Classes are typically implemented such that their methods mutate the the internal state of an instance, for example:

class Card {
  constructor () {
    this.state = 'normal'
  }

  select () {
    this.state = 'selected'
  }
}

const card = new Card()
console.log(card.state) // 'normal'
card.select()
console.log(card.state) // 'selected'

This type of idiom is very common with object oriented programming (OOP), but it certainly isn’t the only way to do things. Let’s change the increment method, so that instead of mutating the original card we create a copy of the card, modify the copy, and return it:

import { set } from 'fkit'

class Card {
  constructor () {
    this.state = state
  }

  select () {
    // The FKit set function preserves the prototype of the
    // object being copied.
    return set('state', 'selected', this)
  }
}

const card = new Card()
console.log(card.state) // 'normal'
const nextCard = card.select()
console.log(nextCard.state) // 'selected'

One key difference worth pointing out between these two examples is that in the mutable example, we lost our reference to the original state. Once we mutated the card, its previous state was gone forever. But in the immutable example, we didn’t lose any history — we have references to both card and nextCard.

This is a subtle but extremely powerful benefit to using immutable data structures. It allows us to do interesting things, like calculate the difference between the two states to see which parts of the UI need repainting, etc. View libraries, such as React, can immediately take advantage of this.

While some people think that using classes leads to unnecessary complexity, and that they should be avoided at all costs, people in the other camp enjoy all the benefits that classes and OOP bring. I’m not here to try to convince you one way or the other, you should do some more reading and decide for yourself. But I wanted to illustrate that classes and immutable data structures aren’t mutually exclusive; you can have your immutable cake and eat it too. Enjoy! 🍰

Josh Bassett

Hello. I'm a software developer living in Byron Bay, Australia.