MLton 20051202

FunctionalRecordUpdate

Home Index

Functional record update is the copying of a record while replacing the values of some of the fields. For example, the functional update of

    {a = 13, b = 14, c = 15}

with `c = 16` yields a new record

    {a = 13, b = 14, c = 16}

Functional record update also makes sense with multiple simultaneous updates. For example, the functional update of the record above with `a = 18, c = 19` yields a new record

    {a = 18, b = 14, c = 19}

Standard ML does not have explicit syntax for functional record update. One could easily imagine an extension of the SML that supported it. For example

    e with {a = 16, b = 17}

would create a copy of the record denoted by `e` with field `a` replaced with `16` and `b` replaced with `17`. Despite the absence of special syntax, it is easy to emulate functional record update with a little boilerplate code.

## Simple implementation

To support functional record update on the record type

    {a: 'a, b: 'b, c: 'c}

first, define an update function for each component.

    fun withA ({a = _, b, c}, a) = {a = a, b = b, c = c}
    fun withB ({a, b = _, c}, b) = {a = a, b = b, c = c}
    fun withC ({a, b, c = _}, c) = {a = a, b = b, c = c}

Then, one can express `e with {a = 16, b = 17}` as

    withB (withA (e, 16), 17)

With infix notation

    infix withA withB withC

the syntax is almost as concise as a language extension.

    e withA 16 withB 17

## Advanced implementation

The above approach suffers from the fact that the amount of boilerplate code is quadratic in the number of record fields. Furthermore, changing, adding, or deleting a field requires time proportional to the number of fields (because each `with` function must be changed). It is also annoying to have to define a `with` function, possibly with a fixity declaration, for each field.

Fortunately, there is a solution to these problems. We can define a single function, `set`, use the existing SML record selector syntax, and the left piping operator, so that

    {a = 1, b = "foo", c = 3.0} >| set#a 13 >| set#b "bar"

will evaluate to

    {a = 13, b = "bar", c = 3.0}

Here is the definition of `set`.

    fun set f z {a, b, c} =
       let
          datatype t = A of 'a | B of 'b | C of 'c
          fun g h z =
             {a = case h z of A a => a | _ => a,
              b = case h z of B b => b | _ => b,
              c = case h z of C c => c | _ => c}
       in
          f {a = g A, b = g B, c = g C} z
       end

Here is the type of `set`.

    val set : ({a:'a -> {a:'a, b:'b, c:'c},
                b:'b -> {a:'a, b:'b, c:'c},
                c:'c -> {a:'a, b:'b, c:'c}} -> 'd -> 'e)
              -> 'd
              -> {a:'a, b:'b, c:'c}
              -> 'e

To change a field with this approach, we only have to change three things.

- the variant in `datatype t`

- the field in the result of g

- the field in the argument to `f`

There is a minor disadvantage, however. The type of the field being updated can not (easily) be changed:

    {a=1, b=2, c=3} >| set#a "1" (* Type error! *)

While our definition of `set` is valid SML and works with MLton, unfortunately, most other SML compilers mistakenly reject the program because of the free type variables in the datatype declaration. You can work around this problem in such compilers by manually lifting `datatype t` to the toplevel and adding `'a`, `'b`, and `'c` as parameters to `t`.

## Going Further

One can generalize the previous approach and define a function that performs functional record update on any object that is isomorphic to a tuple (of the appropriate arity).

We first define a function to perform a functional 3-tuple update:

    fun set3 f v (v1, v2, v3) =
        let
           datatype ('v1, 'v2, 'v3) t =
                    V1 of 'v1 | V2 of 'v2 | V3 of 'v3
           fun g h v =
               (case h v of V1 v1 => v1 | _ => v1,
                case h v of V2 v2 => v2 | _ => v2,
                case h v of V3 v3 => v3 | _ => v3)
        in
           f (g V1, g V2, g V3) v
        end

We also define a generic function for wrapping a tuple update given an isomorphism:

    fun wrapSet (set, t2r, t2r', r2t) f v r = t2r (set (f o t2r') v (r2t r))

The isomorphism is specified by `t2r`, `t2r'`, and `r2t`; `t2r` and `t2r'` are actually the same function - we need to supply two copies because of the absence of FirstClassPolymorphism in SML.

Here's how to use `set3` and `wrapSet` to define an update function for `{a, b, c`} and for `{d, e, f`}.

    fun set f =
        let
           fun t2r (v1, v2, v3) = {a = v1, b = v2, c = v3}
           fun r2t {a = v1, b = v2, c = v3} = (v1, v2, v3)
        in
           wrapSet (set3, t2r, t2r, r2t) f
        end

    fun set f =
        let
           fun t2r (v1, v2, v3) = {d = v1, e = v2, f = v3}
           fun r2t {d = v1, e = v2, f = v3} = (v1, v2, v3)
        in
           wrapSet (set3, t2r, t2r, r2t) f
        end

With this approach, changing a field name only requires changing the name in the `t2r` and `r2t` functions.

The MLton SVN contains Emacs functions in esml-gen.el to generate functional tuple update functions and functional record update functions. For example, to generate a `set` function for the record `{a, b, c`} it is sufficient to type `M x esml-gen-fru-setter a b c`.

## Efficiency

With MLton, the efficiency of these approaches is as good as one would expect with the special syntax. Namely a sequence of updates will be optimized into a single record construction that copies the unchanged fields and fills in the changed fields with their new values.

## Imperative approach

One can use ref cells under the hood to implement functional record update.

    fun set f z {a, b, c} =
       let
          val a = ref a
          val b = ref b
          val c = ref c
          val () = f {a = a, b = b, c = c} := z
       in
          {a = !a, b = !b, c = !c}
       end

Last edited on 2005-08-14 18:21:47 by VesaKarvonen.