As an example, the functional update of the record
{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}
One could easily imagine an extension of the SML that supports functional record update. 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.
Since there is no such syntax in SML, we now show how to implement functional record update directly. We first give a simple implementation that has a number of problems. We then give an advanced implementation, that, while complex underneath, is a reusable library that admits simple use.
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 withCthe syntax is almost as concise as a language extension.
e withA 16 withB 17
This 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.
Advanced implementation
Using Fold one can define a family of makeUpdate<N> functions and single update operator U so that one can define a functional record update function for any record type simply by specifying a (trivial) isomorphism between that type and a product type. For example, suppose that we would like to do functional record update on records with fields a and b. Then one defines a function updateAB as follows.
val updateAB =
fn z =>
let
fun p2r (v1 & v2) = {a = v1, b = v2}
fun r2p {a = v1, b = v2} = (v1 & v2)
in
makeUpdate2 (p2r, p2r, r2p)
end
z
The functions p2r (think product to record) and r2p (think record to product) specify an isomorphism between a,b records and binary products. There is a second use of p2r to work around the lack of first-class polymorphism in SML.
With the definition of updateAB in place, the following expressions are valid.
updateAB {a = 13, b = "hello"} (U#b "goodbye") $
updateAB {a = 13.5, b = true} (U#b false) (U#a 12.5) $
As another example, suppose that we would like to do functional record update on records with fields b, c, and d. Then one defines a function updateBCD as follows.
val updateBCD =
fn z =>
let
fun p2r (v1 & v2 & v3) = {b = v1, c = v2, d = v3}
fun r2p {b = v1, c = v2, d = v3} = (v1 & v2 & v3)
in
makeUpdate3 (p2r, p2r, r2p)
end
z
With the definition of updateBCD in place, the following expression is valid.
updateBCD {b = 1, c = 2, d = 3} (U#c 4) (U#c 5) $
Note that not all fields need be updated and that the same field may be updated multiple times. Further note that the same U operator is used for all update functions (in the above, for both updateAB and updateBCD).
In general, to define a functional-record-update function on records with fields f1, f2, ..., fN, use the following template.
val update =
fn z =>
let
fun p2r (v1 & v2 & ... & vn) = {f1 = v1, f2 = v2, ..., fn = vn}
fun r2p {f1 = v1, f2 = v2, ..., fn = vn} = (v1 & v2 & ... & vn)
in
makeUpdateN (p2r, p2r, r2p)
end
z
With this, one can update a record as follows.
update {f1 = v1, ..., fn = vn} (U#fi1 vi1) ... (U#fim vim) $
If makeUpdateN is not already defined for the desired N, a generic makeUpdate function and special value, A, is defined so that one can use the following for makeUpdateN, where A is repeated N times.
makeUpdate A ... A $
The FunctionalRecordUpdate structure
Here is the implementation of functional record update.
structure FunctionalRecordUpdate =
struct
datatype ('x, 'y) u = X of 'x | Y of 'y
val makeUpdate =
fn z =>
Fold.fold
(((), (),
fn f => f o X,
fn (a, u) => case u of X x => x | _ => a),
fn (p, up, _, _) => fn (p2r, p2r', r2p) => fn r =>
Fold.fold ((p2r' (p id), up, r2p r),
fn (_, _, p) => p2r p))
z
val A =
fn z =>
Fold.step0
(fn (_, _, p, up) =>
(p, up, fn f => p (f o X) & (f o Y),
fn (a & b, u) =>
(case u of X x => up (a, x) | _ => a)
& (case u of Y y => y | _ => b)))
z
fun makeUpdate2 z = makeUpdate A A $ z
fun makeUpdate3 z = makeUpdate A A A $ z
fun makeUpdate4 z = makeUpdate A A A A $ z
fun U s v = Fold.step0 (fn (r, up, p) => (r, up, up (p, s r v)))
end
The idea of makeUpdate is to inductively build the update function for n-ary product types. Each A supplied to makeUpdate adds one more level to the product. When finished with its arguments, makeUpdate begins a second fold, this time to process a variable number of U steps. The second fold begins by converting the supplied record to a product, using the supplied isomorphism (p2r'). Each step works by selecting a "path", s r v), from the inductively constructed product, reformatted by the supplied isomorphism to look like a record. Then, the inductively constructed update function is applied to the record-as-product and the path up (p, s r v) to yield a new record-as-product. Finally, at the end of the fold, the product is converted back to a record using the supplied isomorphism (p2r).
Efficiency
With MLton, the efficiency of this approach 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.