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
Tries are prefix or radix based search trees.
Henceforth: RADIX TREES
Why can't we just have a data structure without any tradeoffs?
DO YOU HAVE A MOMENT TO TALK ABOUT
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!
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