// Juanpe Bolívar
// https://sinusoid.al

postmodern

immutable

data structures

Part I

The tragedy
of the
value based
architecture

mutability ⇒ ( pass by value ⇒ copying )

root cause cause problem


const auto v0 = vector<int>{};
const auto v1 = v0.push_back(15);
const auto v2 = v1.push_back(16);
const auto v3 = v2.set(0, 42);


assert(v2.size() == v0.size() + 2);
assert(v3[0] - v1[0] == 27);

immutable data structure

one with all methods
marked const

persistent data structure

old values are preserved

structural sharing

no copying
compact history
fast comparison

immer
a library of immutable data structures

https://sinusoid.es/immer

idiomatic
this is C++ not Haskell
performant
cache-efficient, benchmark-driven
customizable
stackable allocators, optional GC, thread-safety

Part II

in search of a magical vector


const auto v0 = list<char>{{'a'}};
const auto v1 = v0.push_front('b')
                  .push_front('c');
const auto v2 = v1.push_front('d');
const auto v3 = v1.push_front('e');

Chris Okasaki
Purely Functional Data Structures
https://www.cs.cmu.edu/~rwh/theses/okasaki.pdf

Ralf Hinze and Ross Paterson
Finger Trees: A General-purpose Data Structure
http://www.staff.city.ac.uk/~ross/papers/FingerTree.html

Phil Bagwell
Array Mapped Tries. 2000
RRB-Trees: Efficient Immutable Vectors. 2011
https://infoscience.epfl.ch/record/64394/files/triesearches.pdf https://infoscience.epfl.ch/record/169879/files/RMTrees.pdf

Rich Hickey
Value, Identity and State. 2009
https://www.infoq.com/presentations/Value-Identity-State-Rich-Hickey

Radix Balanced Tree

$M=2^B$ $M=32$ $B=5$ $\left\lceil\log_{32}(2^{32})\right\rceil = 7$

Radix Balanced Search

v[17] → 01 00 01 v.set(17, 'R')

Relaxed Radix Balanced Tree

Operations

$$\text{effective}\ O(1)$$

Random access
Update
Push back
Slice right/right

$$O(\log(n))$$

Concat
Insert
Push front

Embedding
Radix balanced tree

$$M=2^B$$ $$M_l=2^{B_l}$$

$$ B_l^{\mathit{opt}}(B, T) = \left\lfloor \log_2\left( \frac{\mathit{sizeof}_* \times 2^B} {\mathit{sizeof}_T} \right) \right\rfloor $$


vector<int> myiota(vector<int> v, int first, int last)
{
    for (auto i = first; i < last; ++i)
        v = v.push_back(i);
    return v;
}


vector<int> myiota(vector<int> v, int first, int last)
{
    auto t = v.transient();
    for (auto i = first; i < last; ++i)
        t.push_back(i);
    return t.persistent();
}


vector<int> myiota(vector<int> v, int first, int last)
{
    auto t = v.transient();
    std::generate_n(std::back_inserter(t),
                    last - first,
                    [&] { return first++; });
    return t.persistent();
}

reference counting ➡ r-values are transients


vector<char> say_hi(vector<char> v)
{
    return v.push_back('h')        ⟵―― named value: v
    return move(v).push_back('h')  ⟵―― r-value value
            .push_back('i')        ⟵―― r-value value
            .push_back('!');       ⟵―― r-value value
}

and they compose ➡ say_hi(say_hi(...))


vector<int> myiota(vector<int> v, int first, int last)
{
    for (auto i = first; i < last; ++i)
        v = std::move(v).push_back(i);
    return v;
}

The Holy Grail

A Hash Array Mapped
Trie for C++

Phil Nash

https://www.youtube.com/watch?v=imrSQ82dYns

Is this fast?

Summing a $10^5$ element vector ($\mu s$)

Ten $10^4$ element concatenations ($\mu s$)

Building a $10^5$ element vector ($\mu s$)

Building a $10^5$ element transient vector ($\mu s$)

Mutating all $10^5$ element vector ($\mu s$)

Mutating all $10^5$ element transient vector ($\mu s$)

YES.

Interlude

Ewig
an example application

Part III

Redemption for the
value based architecture


application update(application state, action ev);

void run(const char* fname)
{
    auto term  = terminal{};
    auto state = application{load_buffer(fname), key_map_emacs};
    while (!state.done) {
        draw(state);
        auto act = term.next();
        state = update(state, act);
    }
}


using index = int;

struct coord
{
    index row = {};
    index col = {};
};

using line = immer::flex_vector<char>;
using text = immer::flex_vector<line>;

struct file
{
    immer::box<std::string> name;
    text content;
};

struct snapshot
{
    text content;
    coord cursor;
};


struct buffer
{
    file from;
    text content;
    coord cursor;
    coord scroll;
    std::optional<coord> selection_start;
    immer::vector<snapshot> history;
    std::optional<std::size_t> history_pos;
};

struct application
{
    buffer current;
    key_map keys;
    key_seq input;
    immer::vector<text> clipboard;
    immer::vector<message> messages;
};

struct action { key_code key; coord size; };

example

Undo


edit S1 ♦
edit S1   S2 ♦
edit S1   S2   S3 ♦
edit S1   S2   S3   S4 ♦
undo S1   S2   S3 ♦ S4   S3
undo S1   S2 ♦ S3   S4   S3   S2
edit S1   S2   S3   S4   S3   S2  S5 ♦

Emacs-style undo

Never loose work
Undo is undoable


buffer record(buffer before, buffer after)
{
    if (before.content != after.content) {
        after.history = after.history.push_back({before.content, before.cursor});
        if (before.history_pos == after.history_pos)
            after.history_pos = std::nullopt;
    }
    return after;
}

buffer undo(buffer buf)
{
    auto idx = buf.history_pos.value_or(buf.history.size());
    if (idx > 0) {
        auto restore = buf.history[--idx];
        buf.content = restore.content;
        buf.cursor = restore.cursor;
        buf.history_pos = idx;
    }
    return buf;
  }


buffer record(buffer before, buffer after)
{
    if (before.content != after.content) {
        after.history = after.history.push_back({before.content, before.cursor});
        if (before.history_pos == after.history_pos)
            after.history_pos = std::nullopt;
    }
    return after;
}

buffer undo(buffer buf)
{
    auto idx = buf.history_pos.value_or(buf.history.size());
    if (idx > 0) {
        auto restore = buf.history[--idx];
        buf.content = restore.content;
        buf.cursor = restore.cursor;
        buf.history_pos = idx;
    }
    return buf;
  }