Lager: Unidirectional data-flow for C++ inspired by Redux and Elm (sinusoid.es)

One thing I'd love to explore (but can't because of my employer's IP policies) is how to get selectors running in sublinear time the same way "immutable data structures" get reducers to run in sublinear time.

Like, for an "add order" action, in a redux app you might often see something like

    return [...oldState.orders, newOrder];

Or, for the Python-inclined,

    return old_state.orders + [new_order]

Which is great, no chance anyone playing with the new array of widgets will mess up anyone looking at the old array of widgets, but terrible because we've bought that safety by making that "update" (which in an old-school app would have been an amortised constant-time append) into a linear time array concatenation. And the same thing happens with hash table insertions+deletions.

So someone invents immutable data structures (like Clojure has, and like Immer and Immutable.js and probably any number of nice libraries) that use trees under the hood for their "arrays" and "maps" to get those operations down to logarithmic time while preserving the nice "value-copying" semantics.

But then for a redux app you might make a selector to calculate some "derived state" from your base data. Maybe you want to show the total price of all orders to a user, so you write a pure functional selector to do it:

    totalPrice = state => {
      total = 0;
      state.orders.forEach(order => {
        total += order.price;
      });
      return total:
    };

or in Python,

    def total_price(state):
        return sum(order.price for order in state.orders)

And maybe you memoize that function based on the identity of `state` in case you call it a bunch with the same input. And that's all well and good, but that calculation takes linear time, so when you add an order your view update is still going to take linear time.

In the "bad old days", when you were mutating orders and getting a constant-time append, you'd probably have a variable somewhere to store the total price, and you'd do a `+=` when adding an order, getting a constant time update of the total price.

Is there some way to get back to sublinear time, like we did with updates to underlying state?

I think so. Remember that immutable data structures (mostly?) use trees under the hood. "Appending" an item to an "array" makes a new tree, where almost all of the nodes are shared with the old tree, and a small number (including the root) are new. Naively, the root's left child is from the old tree and its right child is new, and its right child's left child is old, and its right child's right child is new, all the way down to the new rightmost element.

If we could memoize `totalPrice` for subtrees, we could calculate the updated sum in log time. We would get the total for the each node's left child in constant time (because they'd be memoized), and only have to do any new computation for the new nodes in the tree down the "right-right-right" path.

Anyway, I don't know if a data structures library could make this ergonomic enough to make any added efficiencies worthwhile, and I'd love to program it up and play with it and find out, but aforementioned employer prohibitions mean this is probably always going to be just a thought experiment.

Thanks all for taking a look. I would like to thank Prenav for sponsoring the documentation effort and some of the latest developments (https://www.prenav.com). Good supporters of open source <3