Efficient updates for closed records in PureScript

In JavaScript you can change the value of a field in a record like this:

var r = {a: 5, b: 7};
r.b = 9;                // or r["b"] = 9;
console.log(r);         // {a: 5, b: 9}

PureScript’s records are immutable. “Updating” a record field returns a new record with the updated field, but leaves the original record untouched.

-- assume some unsafe  log :: forall a. a -> Eff ()
do
  let r = {a: 5, b: 7}
  let r' = r { b = 9 }
  log r                  -- {a: 5, b: 7}
  log r'                 -- {a: 5, b: 9}

The record update itself compiles to something like this:

var r = {a: 5, b: 7}
var r' = (function () {
  var res = {};
  for (var f in r) {
     if (Object.prototype.hasOwnProperty.call(r, f)) {
        res[f] = r[f];
     }
  }
  res.b=9;
  return res;
})()

First we make a copy of the record being updated, r in this case. Then we (destructively) update the field in the copy. PureScript compiles to ES3, otherwise we could use Object.assign (ES6, not in IE) instead like this: Object.assign({}, r, {b: 9}).

Enter types

PureScript is a statically typed language and has built-in record types. The type of r and r' above is {a :: Int, b :: Int}. Given this information, we can generate better code for record updates. Because we know exactly which fields get new values and which fields take their value from the input record, we can just construct the right new record without iterating over the input record. In our example that would look something like this:

var r = {a: 5, b: 7}
var r' = {a: r.a, b: 9}  // no update, just construct the right record

This is around 100 times faster in both Firefox and Chrome.¹

Open records

PureScript supports row polymorphism. Which means that expressions, in particular functions, can operate on records of different shapes. An open record type looks like this: {b :: Int | foo}. This indicates a record that has at least a field b with type Int, but the rest of the record’s fields are indicated by the type variable foo. This allows us to write a function like the following which increases the integer-valued field count of any record:

incCount :: forall row. { count :: Int | row } ->  { count :: Int | row }
incCount r = r { count = r.count + 1 }

Because we don’t know exactly what fields the record will have, we cannot use this trick to compile incCount. We have to fall back to using the loop, or perhaps Object.assign in the future.

Conclusions

This turned out to be very easy to implement,² so PureScript 0.12 will generate better code for closed record updates thanks to types.