Commit | Line | Data |
---|---|---|
7f918cf1 CE |
1 | FunctionalRecordUpdate |
2 | ====================== | |
3 | ||
4 | Functional record update is the copying of a record while replacing | |
5 | the values of some of the fields. <:StandardML:Standard ML> does not | |
6 | have explicit syntax for functional record update. We will show below | |
7 | how to implement functional record update in SML, with a little | |
8 | boilerplate code. | |
9 | ||
10 | As an example, the functional update of the record | |
11 | ||
12 | [source,sml] | |
13 | ---- | |
14 | {a = 13, b = 14, c = 15} | |
15 | ---- | |
16 | ||
17 | with `c = 16` yields a new record | |
18 | ||
19 | [source,sml] | |
20 | ---- | |
21 | {a = 13, b = 14, c = 16} | |
22 | ---- | |
23 | ||
24 | Functional record update also makes sense with multiple simultaneous | |
25 | updates. For example, the functional update of the record above with | |
26 | `a = 18, c = 19` yields a new record | |
27 | ||
28 | [source,sml] | |
29 | ---- | |
30 | {a = 18, b = 14, c = 19} | |
31 | ---- | |
32 | ||
33 | ||
34 | One could easily imagine an extension of the SML that supports | |
35 | functional record update. For example | |
36 | ||
37 | [source,sml] | |
38 | ---- | |
39 | e with {a = 16, b = 17} | |
40 | ---- | |
41 | ||
42 | would create a copy of the record denoted by `e` with field `a` | |
43 | replaced with `16` and `b` replaced with `17`. | |
44 | ||
45 | Since there is no such syntax in SML, we now show how to implement | |
46 | functional record update directly. We first give a simple | |
47 | implementation that has a number of problems. We then give an | |
48 | advanced implementation, that, while complex underneath, is a reusable | |
49 | library that admits simple use. | |
50 | ||
51 | ||
52 | == Simple implementation == | |
53 | ||
54 | To support functional record update on the record type | |
55 | ||
56 | [source,sml] | |
57 | ---- | |
58 | {a: 'a, b: 'b, c: 'c} | |
59 | ---- | |
60 | ||
61 | first, define an update function for each component. | |
62 | ||
63 | [source,sml] | |
64 | ---- | |
65 | fun withA ({a = _, b, c}, a) = {a = a, b = b, c = c} | |
66 | fun withB ({a, b = _, c}, b) = {a = a, b = b, c = c} | |
67 | fun withC ({a, b, c = _}, c) = {a = a, b = b, c = c} | |
68 | ---- | |
69 | ||
70 | Then, one can express `e with {a = 16, b = 17}` as | |
71 | ||
72 | [source,sml] | |
73 | ---- | |
74 | withB (withA (e, 16), 17) | |
75 | ---- | |
76 | ||
77 | With infix notation | |
78 | ||
79 | [source,sml] | |
80 | ---- | |
81 | infix withA withB withC | |
82 | ---- | |
83 | ||
84 | the syntax is almost as concise as a language extension. | |
85 | ||
86 | [source,sml] | |
87 | ---- | |
88 | e withA 16 withB 17 | |
89 | ---- | |
90 | ||
91 | This approach suffers from the fact that the amount of boilerplate | |
92 | code is quadratic in the number of record fields. Furthermore, | |
93 | changing, adding, or deleting a field requires time proportional to | |
94 | the number of fields (because each ++with__<L>__++ function must be | |
95 | changed). It is also annoying to have to define a ++with__<L>__++ | |
96 | function, possibly with a fixity declaration, for each field. | |
97 | ||
98 | Fortunately, there is a solution to these problems. | |
99 | ||
100 | ||
101 | == Advanced implementation == | |
102 | ||
103 | Using <:Fold:> one can define a family of ++makeUpdate__<N>__++ | |
104 | functions and single _update_ operator `U` so that one can define a | |
105 | functional record update function for any record type simply by | |
106 | specifying a (trivial) isomorphism between that type and function | |
107 | argument list. For example, suppose that we would like to do | |
108 | functional record update on records with fields `a` and `b`. Then one | |
109 | defines a function `updateAB` as follows. | |
110 | ||
111 | [source,sml] | |
112 | ---- | |
113 | val updateAB = | |
114 | fn z => | |
115 | let | |
116 | fun from v1 v2 = {a = v1, b = v2} | |
117 | fun to f {a = v1, b = v2} = f v1 v2 | |
118 | in | |
119 | makeUpdate2 (from, from, to) | |
120 | end | |
121 | z | |
122 | ---- | |
123 | ||
124 | The functions `from` (think _from function arguments_) and `to` (think | |
125 | _to function arguements_) specify an isomorphism between `a`,`b` | |
126 | records and function arguments. There is a second use of `from` to | |
127 | work around the lack of | |
128 | <:FirstClassPolymorphism:first-class polymorphism> in SML. | |
129 | ||
130 | With the definition of `updateAB` in place, the following expressions | |
131 | are valid. | |
132 | ||
133 | [source,sml] | |
134 | ---- | |
135 | updateAB {a = 13, b = "hello"} (set#b "goodbye") $ | |
136 | updateAB {a = 13.5, b = true} (set#b false) (set#a 12.5) $ | |
137 | ---- | |
138 | ||
139 | As another example, suppose that we would like to do functional record | |
140 | update on records with fields `b`, `c`, and `d`. Then one defines a | |
141 | function `updateBCD` as follows. | |
142 | ||
143 | [source,sml] | |
144 | ---- | |
145 | val updateBCD = | |
146 | fn z => | |
147 | let | |
148 | fun from v1 v2 v3 = {b = v1, c = v2, d = v3} | |
149 | fun to f {b = v1, c = v2, d = v3} = f v1 v2 v3 | |
150 | in | |
151 | makeUpdate3 (from, from, to) | |
152 | end | |
153 | z | |
154 | ---- | |
155 | ||
156 | With the definition of `updateBCD` in place, the following expression | |
157 | is valid. | |
158 | ||
159 | [source,sml] | |
160 | ---- | |
161 | updateBCD {b = 1, c = 2, d = 3} (set#c 4) (set#c 5) $ | |
162 | ---- | |
163 | ||
164 | Note that not all fields need be updated and that the same field may | |
165 | be updated multiple times. Further note that the same `set` operator | |
166 | is used for all update functions (in the above, for both `updateAB` | |
167 | and `updateBCD`). | |
168 | ||
169 | In general, to define a functional-record-update function on records | |
170 | with fields `f1`, `f2`, ..., `fN`, use the following template. | |
171 | ||
172 | [source,sml] | |
173 | ---- | |
174 | val update = | |
175 | fn z => | |
176 | let | |
177 | fun from v1 v2 ... vn = {f1 = v1, f2 = v2, ..., fn = vn} | |
178 | fun to f {f1 = v1, f2 = v2, ..., fn = vn} = v1 v2 ... vn | |
179 | in | |
180 | makeUpdateN (from, from, to) | |
181 | end | |
182 | z | |
183 | ---- | |
184 | ||
185 | With this, one can update a record as follows. | |
186 | ||
187 | [source,sml] | |
188 | ---- | |
189 | update {f1 = v1, ..., fn = vn} (set#fi1 vi1) ... (set#fim vim) $ | |
190 | ---- | |
191 | ||
192 | ||
193 | == The `FunctionalRecordUpdate` structure == | |
194 | ||
195 | Here is the implementation of functional record update. | |
196 | ||
197 | [source,sml] | |
198 | ---- | |
199 | structure FunctionalRecordUpdate = | |
200 | struct | |
201 | local | |
202 | fun next g (f, z) x = g (f x, z) | |
203 | fun f1 (f, z) x = f (z x) | |
204 | fun f2 z = next f1 z | |
205 | fun f3 z = next f2 z | |
206 | ||
207 | fun c0 from = from | |
208 | fun c1 from = c0 from f1 | |
209 | fun c2 from = c1 from f2 | |
210 | fun c3 from = c2 from f3 | |
211 | ||
212 | fun makeUpdate cX (from, from', to) record = | |
213 | let | |
214 | fun ops () = cX from' | |
215 | fun vars f = to f record | |
216 | in | |
217 | Fold.fold ((vars, ops), fn (vars, _) => vars from) | |
218 | end | |
219 | in | |
220 | fun makeUpdate0 z = makeUpdate c0 z | |
221 | fun makeUpdate1 z = makeUpdate c1 z | |
222 | fun makeUpdate2 z = makeUpdate c2 z | |
223 | fun makeUpdate3 z = makeUpdate c3 z | |
224 | ||
225 | fun upd z = Fold.step2 (fn (s, f, (vars, ops)) => (fn out => vars (s (ops ()) (out, f)), ops)) z | |
226 | fun set z = Fold.step2 (fn (s, v, (vars, ops)) => (fn out => vars (s (ops ()) (out, fn _ => v)), ops)) z | |
227 | end | |
228 | end | |
229 | ---- | |
230 | ||
231 | The idea of `makeUpdate` is to build a record of functions which can | |
232 | replace the contents of one argument out of a list of arguments. The | |
233 | functions ++f__<X>__++ replace the 0th, 1st, ... argument with their | |
234 | argument `z`. The ++c__<X>__++ functions pass the first __X__ `f` | |
235 | functions to the record constructor. | |
236 | ||
237 | The `#field` notation of Standard ML allows us to select the map | |
238 | function which replaces the corresponding argument. By converting the | |
239 | record to an argument list, feeding that list through the selected map | |
240 | function and piping the list into the record constructor, functional | |
241 | record update is achieved. | |
242 | ||
243 | ||
244 | == Efficiency == | |
245 | ||
246 | With MLton, the efficiency of this approach is as good as one would | |
247 | expect with the special syntax. Namely a sequence of updates will be | |
248 | optimized into a single record construction that copies the unchanged | |
249 | fields and fills in the changed fields with their new values. | |
250 | ||
251 | Before Sep 14, 2009, this page advocated an alternative implementation | |
252 | of <:FunctionalRecordUpdate:>. However, the old structure caused | |
253 | exponentially increasing compile times. We advise you to switch to | |
254 | the newer version. | |
255 | ||
256 | ||
257 | == Applications == | |
258 | ||
259 | Functional record update can be used to implement labelled | |
260 | <:OptionalArguments:optional arguments>. |