immutable.rs

@bodil

A way of organising data so that it can be accessed and modified efficiently.

A mutable value can change (like Vec), but an immutable value is the same forever (like i32).

A data structure that *persists its current state* when changed.

We need a way to talk about the efficiency of operations on data structures.

Big O notation!

Same amount of work regardless of the size of the data structure.

Number of operations proportional to the size *(n)* of the data structure.

Number of operations logarithmic to the size of the data structure.

O(1) = constant time

O(log n) = logarithmic time

O(n) = linear time

O(n log n) = linear × logarithmic time

Spreading the cost over several operations.

*cadr* = car of cdr = second element

*caddr* = car of cdr of cdr = third element

*cddr* = cdr of cdr = third element onward

*caar* = car of car = first element of first element

head →

tail →

TRIES

and the hardest problem in computer science

Tries are *prefix* or *radix* based search trees.

Henceforth: RADIX TREES

Phil Bagwell

Rich Hickey

Why can't we just have a data structure without any tradeoffs?

DO YOU HAVE A MOMENT TO TALK ABOUT

RELAXED RADIX BALANCED TREES

Push/pop: O(logₖ n)

Lookup: O(logₖ n)

Concat: O(logₖ n)

Split: O(logₖ n)

Immutable values make it easier to reason about your program!

(the Haskell defence)

If a value never changes, you can't have race conditions when changing it.

Recursive algorithms can backtrack easily

Stateful apps can replay state

Cloning is always O(1)!

Its big O isn't that great, but -

It's unbeatable with cache locality

Chunking techniques let us lean on that

Clojure has "transients" for this.

Haskell has the ST monad.

fn Arc::make_mut(this: &mut Arc<T>) -> &mut T

If you're the sole owner, you're always mutable.

RRB vectors do complex things smarter than Vec

With chunking, simpler ops can perform at Vec like speeds

And at small sizes, it literally is Vec!

Memory footprint is only slightly worse than Vec

Maps should perform close to std::collections

…if I've done my job right

Still a slightly worse memory footprint

As complete as Haskell (and Clojure)

But should feel like Rust

Nobody is going to use a library with bad documentation.

Im wraps values in *Arc* to avoid a Clone constraint.

It's slow, so maybe leave it to the user.

*Arc*-less seems to speed things up a LOT!

@bodil

BELKA & STRELKA

Okasaki: *Purely Functional Data Structures*

L'Orange: *Understanding Clojure's Vectors*

Bagwell: *Ideal Hash Trees*

Hinze, Paterson: *Finger Trees*

Acar, Charguéraud, Rainey: *Chunked Sequences*

Stucki, Rompf, Ureche, Bagwell: *RRB Vector*