Show notes

What is it?

Immutable (or persistent) data structures are “append-only” data structures. All representations of it throughout time are kept and accessible through a specific reference.

Partially-persistent vs Fully-persistent

Partially-persistent data structures only allow “modification” of the data structure from the most recent version. This ensures a linear ordering of events. Fully-persistent can modify any reference but can lead to multiple branches / timelines.

Simple examples: Singly-linked list

Why are these useful?

  • They handle concurrency very well
  • Avoids full copy-on-write

Fat Node

Storing all versions of values in the nodes themselves + having a way of differentiating the version

Path Copying

Making new nodes representing the path to new value, while making sure all previous nodes are accessible

Let’s build an Immutable Hash Map!

First, let’s build a regular hash/map/associative array with a trie/prefix tree

  • Advantages
    • Possibly less memory consumption
      • Radix tree
      • Bust also possibly more if no radix and lots of keys and not hashing
    • More structured data
      • Not necessary to hash
      • Full text search
  • Disadvantages
    • Faster lookup in the worst case but slower lookup in the average case

Now let’s make the immutable version!