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