Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] Annotation of /sml/trunk/src/smlnj-lib/Util/redblack-map-fn.sml
ViewVC logotype

Annotation of /sml/trunk/src/smlnj-lib/Util/redblack-map-fn.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 1193 - (view) (download)

1 : monnier 467 (* redblack-map-fn.sml
2 :     *
3 :     * COPYRIGHT (c) 1999 Bell Labs, Lucent Technologies.
4 :     *
5 :     * This code is based on Chris Okasaki's implementation of
6 :     * red-black trees. The linear-time tree construction code is
7 :     * based on the paper "Constructing red-black trees" by Hinze,
8 :     * and the delete function is based on the description in Cormen,
9 :     * Leiserson, and Rivest.
10 :     *
11 :     * A red-black tree should satisfy the following two invariants:
12 :     *
13 :     * Red Invariant: each red node has a black parent.
14 :     *
15 :     * Black Condition: each path from the root to an empty node has the
16 :     * same number of black nodes (the tree's black height).
17 :     *
18 :     * The Red condition implies that the root is always black and the Black
19 :     * condition implies that any node with only one child will be black and
20 :     * its child will be a red leaf.
21 :     *)
22 :    
23 :     functor RedBlackMapFn (K : ORD_KEY) :> ORD_MAP where Key = K =
24 :     struct
25 :    
26 :     structure Key = K
27 :    
28 :     datatype color = R | B
29 :     and 'a tree
30 :     = E
31 :     | T of (color * 'a tree * K.ord_key * 'a * 'a tree)
32 :    
33 :     datatype 'a map = MAP of (int * 'a tree)
34 :    
35 :     fun isEmpty (MAP(_, E)) = true
36 :     | isEmpty _ = false
37 :    
38 :     val empty = MAP(0, E)
39 :    
40 :     fun singleton (xk, x) = MAP(1, T(R, E, xk, x, E))
41 :    
42 :     fun insert (MAP(nItems, m), xk, x) = let
43 :     val nItems' = ref nItems
44 :     fun ins E = (nItems' := nItems+1; T(R, E, xk, x, E))
45 :     | ins (s as T(color, a, yk, y, b)) = (case K.compare(xk, yk)
46 :     of LESS => (case a
47 :     of T(R, c, zk, z, d) => (case K.compare(xk, zk)
48 :     of LESS => (case ins c
49 :     of T(R, e, wk, w, f) =>
50 :     T(R, T(B,e,wk, w,f), zk, z, T(B,d,yk,y,b))
51 :     | c => T(B, T(R,c,zk,z,d), yk, y, b)
52 :     (* end case *))
53 : monnier 475 | EQUAL => T(color, T(R, c, xk, x, d), yk, y, b)
54 : monnier 467 | GREATER => (case ins d
55 :     of T(R, e, wk, w, f) =>
56 :     T(R, T(B,c,zk,z,e), wk, w, T(B,f,yk,y,b))
57 :     | d => T(B, T(R,c,zk,z,d), yk, y, b)
58 :     (* end case *))
59 :     (* end case *))
60 :     | _ => T(B, ins a, yk, y, b)
61 :     (* end case *))
62 : monnier 475 | EQUAL => T(color, a, xk, x, b)
63 : monnier 467 | GREATER => (case b
64 :     of T(R, c, zk, z, d) => (case K.compare(xk, zk)
65 :     of LESS => (case ins c
66 :     of T(R, e, wk, w, f) =>
67 :     T(R, T(B,a,yk,y,e), wk, w, T(B,f,zk,z,d))
68 :     | c => T(B, a, yk, y, T(R,c,zk,z,d))
69 :     (* end case *))
70 : monnier 475 | EQUAL => T(color, a, yk, y, T(R, c, xk, x, d))
71 : monnier 467 | GREATER => (case ins d
72 :     of T(R, e, wk, w, f) =>
73 :     T(R, T(B,a,yk,y,c), zk, z, T(B,e,wk,w,f))
74 :     | d => T(B, a, yk, y, T(R,c,zk,z,d))
75 :     (* end case *))
76 :     (* end case *))
77 :     | _ => T(B, a, yk, y, ins b)
78 :     (* end case *))
79 :     (* end case *))
80 :     val m = ins m
81 :     in
82 :     MAP(!nItems', m)
83 :     end
84 :     fun insert' ((xk, x), m) = insert (m, xk, x)
85 :    
86 :     (* Is a key in the domain of the map? *)
87 :     fun inDomain (MAP(_, t), k) = let
88 :     fun find' E = false
89 :     | find' (T(_, a, yk, y, b)) = (case K.compare(k, yk)
90 :     of LESS => find' a
91 :     | EQUAL => true
92 :     | GREATER => find' b
93 :     (* end case *))
94 :     in
95 :     find' t
96 :     end
97 :    
98 :     (* Look for an item, return NONE if the item doesn't exist *)
99 :     fun find (MAP(_, t), k) = let
100 :     fun find' E = NONE
101 :     | find' (T(_, a, yk, y, b)) = (case K.compare(k, yk)
102 :     of LESS => find' a
103 :     | EQUAL => SOME y
104 :     | GREATER => find' b
105 :     (* end case *))
106 :     in
107 :     find' t
108 :     end
109 :    
110 :     (* Remove an item, returning new map and value removed.
111 :     * Raises LibBase.NotFound if not found.
112 :     *)
113 :     local
114 :     datatype 'a zipper
115 :     = TOP
116 :     | LEFT of (color * K.ord_key * 'a * 'a tree * 'a zipper)
117 :     | RIGHT of (color * 'a tree * K.ord_key * 'a * 'a zipper)
118 :     in
119 :     fun remove (MAP(nItems, t), k) = let
120 :     fun zip (TOP, t) = t
121 :     | zip (LEFT(color, xk, x, b, z), a) = zip(z, T(color, a, xk, x, b))
122 :     | zip (RIGHT(color, a, xk, x, z), b) = zip(z, T(color, a, xk, x, b))
123 :     (* bbZip propagates a black deficit up the tree until either the top
124 :     * is reached, or the deficit can be covered. It returns a boolean
125 :     * that is true if there is still a deficit and the zipped tree.
126 :     *)
127 :     fun bbZip (TOP, t) = (true, t)
128 :     | bbZip (LEFT(B, xk, x, T(R, c, yk, y, d), z), a) = (* case 1L *)
129 :     bbZip (LEFT(R, xk, x, c, LEFT(B, yk, y, d, z)), a)
130 :     | bbZip (LEFT(color, xk, x, T(B, T(R, c, yk, y, d), wk, w, e), z), a) =
131 :     (* case 3L *)
132 :     bbZip (LEFT(color, xk, x, T(B, c, yk, y, T(R, d, wk, w, e)), z), a)
133 :     | bbZip (LEFT(color, xk, x, T(B, c, yk, y, T(R, d, wk, w, e)), z), a) =
134 :     (* case 4L *)
135 :     (false, zip (z, T(color, T(B, a, xk, x, c), yk, y, T(B, d, wk, w, e))))
136 :     | bbZip (LEFT(R, xk, x, T(B, c, yk, y, d), z), a) = (* case 2L *)
137 :     (false, zip (z, T(B, a, xk, x, T(R, c, yk, y, d))))
138 :     | bbZip (LEFT(B, xk, x, T(B, c, yk, y, d), z), a) = (* case 2L *)
139 :     bbZip (z, T(B, a, xk, x, T(R, c, yk, y, d)))
140 :     | bbZip (RIGHT(color, T(R, c, yk, y, d), xk, x, z), b) = (* case 1R *)
141 :     bbZip (RIGHT(R, d, xk, x, RIGHT(B, c, yk, y, z)), b)
142 :     | bbZip (RIGHT(color, T(B, T(R, c, wk, w, d), yk, y, e), xk, x, z), b) =
143 :     (* case 3R *)
144 :     bbZip (RIGHT(color, T(B, c, wk, w, T(R, d, yk, y, e)), xk, x, z), b)
145 :     | bbZip (RIGHT(color, T(B, c, yk, y, T(R, d, wk, w, e)), xk, x, z), b) =
146 :     (* case 4R *)
147 :     (false, zip (z, T(color, c, yk, y, T(B, T(R, d, wk, w, e), xk, x, b))))
148 :     | bbZip (RIGHT(R, T(B, c, yk, y, d), xk, x, z), b) = (* case 2R *)
149 :     (false, zip (z, T(B, T(R, c, yk, y, d), xk, x, b)))
150 :     | bbZip (RIGHT(B, T(B, c, yk, y, d), xk, x, z), b) = (* case 2R *)
151 :     bbZip (z, T(B, T(R, c, yk, y, d), xk, x, b))
152 :     | bbZip (z, t) = (false, zip(z, t))
153 :     fun delMin (T(R, E, yk, y, b), z) = (yk, y, (false, zip(z, b)))
154 :     | delMin (T(B, E, yk, y, b), z) = (yk, y, bbZip(z, b))
155 :     | delMin (T(color, a, yk, y, b), z) = delMin(a, LEFT(color, yk, y, b, z))
156 : monnier 498 | delMin (E, _) = raise Match
157 : monnier 467 fun join (R, E, E, z) = zip(z, E)
158 :     | join (_, a, E, z) = #2(bbZip(z, a)) (* color = black *)
159 :     | join (_, E, b, z) = #2(bbZip(z, b)) (* color = black *)
160 :     | join (color, a, b, z) = let
161 :     val (xk, x, (needB, b')) = delMin(b, TOP)
162 :     in
163 :     if needB
164 :     then #2(bbZip(z, T(color, a, xk, x, b')))
165 :     else zip(z, T(color, a, xk, x, b'))
166 :     end
167 :     fun del (E, z) = raise LibBase.NotFound
168 :     | del (T(color, a, yk, y, b), z) = (case K.compare(k, yk)
169 :     of LESS => del (a, LEFT(color, yk, y, b, z))
170 :     | EQUAL => (y, join (color, a, b, z))
171 :     | GREATER => del (b, RIGHT(color, a, yk, y, z))
172 :     (* end case *))
173 :     val (item, t) = del(t, TOP)
174 :     in
175 :     (MAP(nItems-1, t), item)
176 :     end
177 :     end (* local *)
178 :    
179 :     (* return the first item in the map (or NONE if it is empty) *)
180 :     fun first (MAP(_, t)) = let
181 :     fun f E = NONE
182 :     | f (T(_, E, _, x, _)) = SOME x
183 :     | f (T(_, a, _, _, _)) = f a
184 :     in
185 :     f t
186 :     end
187 :     fun firsti (MAP(_, t)) = let
188 :     fun f E = NONE
189 :     | f (T(_, E, xk, x, _)) = SOME(xk, x)
190 :     | f (T(_, a, _, _, _)) = f a
191 :     in
192 :     f t
193 :     end
194 :    
195 :     (* Return the number of items in the map *)
196 :     fun numItems (MAP(n, _)) = n
197 :    
198 :     fun foldl f = let
199 :     fun foldf (E, accum) = accum
200 :     | foldf (T(_, a, _, x, b), accum) =
201 :     foldf(b, f(x, foldf(a, accum)))
202 :     in
203 :     fn init => fn (MAP(_, m)) => foldf(m, init)
204 :     end
205 :     fun foldli f = let
206 :     fun foldf (E, accum) = accum
207 :     | foldf (T(_, a, xk, x, b), accum) =
208 :     foldf(b, f(xk, x, foldf(a, accum)))
209 :     in
210 :     fn init => fn (MAP(_, m)) => foldf(m, init)
211 :     end
212 :    
213 :     fun foldr f = let
214 :     fun foldf (E, accum) = accum
215 :     | foldf (T(_, a, _, x, b), accum) =
216 :     foldf(a, f(x, foldf(b, accum)))
217 :     in
218 :     fn init => fn (MAP(_, m)) => foldf(m, init)
219 :     end
220 :     fun foldri f = let
221 :     fun foldf (E, accum) = accum
222 :     | foldf (T(_, a, xk, x, b), accum) =
223 :     foldf(a, f(xk, x, foldf(b, accum)))
224 :     in
225 :     fn init => fn (MAP(_, m)) => foldf(m, init)
226 :     end
227 :    
228 :     fun listItems m = foldr (op ::) [] m
229 :     fun listItemsi m = foldri (fn (xk, x, l) => (xk, x)::l) [] m
230 :    
231 :     (* return an ordered list of the keys in the map. *)
232 :     fun listKeys m = foldri (fn (k, _, l) => k::l) [] m
233 :    
234 :     (* functions for walking the tree while keeping a stack of parents
235 :     * to be visited.
236 :     *)
237 :     fun next ((t as T(_, _, _, _, b))::rest) = (t, left(b, rest))
238 :     | next _ = (E, [])
239 :     and left (E, rest) = rest
240 :     | left (t as T(_, a, _, _, _), rest) = left(a, t::rest)
241 :     fun start m = left(m, [])
242 :    
243 :     (* given an ordering on the map's range, return an ordering
244 :     * on the map.
245 :     *)
246 :     fun collate cmpRng = let
247 :     fun cmp (t1, t2) = (case (next t1, next t2)
248 :     of ((E, _), (E, _)) => EQUAL
249 :     | ((E, _), _) => LESS
250 :     | (_, (E, _)) => GREATER
251 :     | ((T(_, _, xk, x, _), r1), (T(_, _, yk, y, _), r2)) => (
252 :     case Key.compare(xk, yk)
253 :     of EQUAL => (case cmpRng(x, y)
254 :     of EQUAL => cmp (r1, r2)
255 :     | order => order
256 :     (* end case *))
257 :     | order => order
258 :     (* end case *))
259 :     (* end case *))
260 :     in
261 :     fn (MAP(_, m1), MAP(_, m2)) => cmp (start m1, start m2)
262 :     end
263 :    
264 : monnier 475 (* support for constructing red-black trees in linear time from increasing
265 :     * ordered sequences (based on a description by R. Hinze). Note that the
266 :     * elements in the digits are ordered with the largest on the left, whereas
267 :     * the elements of the trees are ordered with the largest on the right.
268 : monnier 467 *)
269 :     datatype 'a digit
270 :     = ZERO
271 :     | ONE of (K.ord_key * 'a * 'a tree * 'a digit)
272 :     | TWO of (K.ord_key * 'a * 'a tree * K.ord_key * 'a * 'a tree * 'a digit)
273 : monnier 475 (* add an item that is guaranteed to be larger than any in l *)
274 : monnier 467 fun addItem (ak, a, l) = let
275 :     fun incr (ak, a, t, ZERO) = ONE(ak, a, t, ZERO)
276 :     | incr (ak1, a1, t1, ONE(ak2, a2, t2, r)) =
277 :     TWO(ak1, a1, t1, ak2, a2, t2, r)
278 :     | incr (ak1, a1, t1, TWO(ak2, a2, t2, ak3, a3, t3, r)) =
279 : monnier 475 ONE(ak1, a1, t1, incr(ak2, a2, T(B, t3, ak3, a3, t2), r))
280 : monnier 467 in
281 :     incr(ak, a, E, l)
282 :     end
283 : monnier 475 (* link the digits into a tree *)
284 : monnier 467 fun linkAll t = let
285 :     fun link (t, ZERO) = t
286 : monnier 475 | link (t1, ONE(ak, a, t2, r)) = link(T(B, t2, ak, a, t1), r)
287 : monnier 467 | link (t, TWO(ak1, a1, t1, ak2, a2, t2, r)) =
288 : monnier 475 link(T(B, T(R, t2, ak2, a2, t1), ak1, a1, t), r)
289 : monnier 467 in
290 :     link (E, t)
291 :     end
292 :    
293 :     local
294 :     fun wrap f (MAP(_, m1), MAP(_, m2)) = let
295 :     val (n, result) = f (start m1, start m2, 0, ZERO)
296 :     in
297 :     MAP(n, linkAll result)
298 :     end
299 :     fun ins ((E, _), n, result) = (n, result)
300 :     | ins ((T(_, _, xk, x, _), r), n, result) =
301 :     ins(next r, n+1, addItem(xk, x, result))
302 :     in
303 :    
304 :     (* return a map whose domain is the union of the domains of the two input
305 :     * maps, using the supplied function to define the map on elements that
306 :     * are in both domains.
307 :     *)
308 :     fun unionWith mergeFn = let
309 :     fun union (t1, t2, n, result) = (case (next t1, next t2)
310 :     of ((E, _), (E, _)) => (n, result)
311 :     | ((E, _), t2) => ins(t2, n, result)
312 :     | (t1, (E, _)) => ins(t1, n, result)
313 :     | ((T(_, _, xk, x, _), r1), (T(_, _, yk, y, _), r2)) => (
314 :     case Key.compare(xk, yk)
315 :     of LESS => union (r1, t2, n+1, addItem(xk, x, result))
316 :     | EQUAL =>
317 :     union (r1, r2, n+1, addItem(xk, mergeFn(x, y), result))
318 :     | GREATER => union (t1, r2, n+1, addItem(yk, y, result))
319 :     (* end case *))
320 :     (* end case *))
321 :     in
322 :     wrap union
323 :     end
324 :     fun unionWithi mergeFn = let
325 :     fun union (t1, t2, n, result) = (case (next t1, next t2)
326 :     of ((E, _), (E, _)) => (n, result)
327 :     | ((E, _), t2) => ins(t2, n, result)
328 :     | (t1, (E, _)) => ins(t1, n, result)
329 :     | ((T(_, _, xk, x, _), r1), (T(_, _, yk, y, _), r2)) => (
330 :     case Key.compare(xk, yk)
331 :     of LESS => union (r1, t2, n+1, addItem(xk, x, result))
332 :     | EQUAL => union (
333 :     r1, r2, n+1, addItem(xk, mergeFn(xk, x, y), result))
334 :     | GREATER => union (t1, r2, n+1, addItem(yk, y, result))
335 :     (* end case *))
336 :     (* end case *))
337 :     in
338 :     wrap union
339 :     end
340 :    
341 :     (* return a map whose domain is the intersection of the domains of the
342 :     * two input maps, using the supplied function to define the range.
343 :     *)
344 :     fun intersectWith mergeFn = let
345 :     fun intersect (t1, t2, n, result) = (case (next t1, next t2)
346 :     of ((T(_, _, xk, x, _), r1), (T(_, _, yk, y, _), r2)) => (
347 :     case Key.compare(xk, yk)
348 :     of LESS => intersect (r1, t2, n, result)
349 :     | EQUAL =>
350 :     intersect (r1, r2, n+1,
351 :     addItem(xk, mergeFn(x, y), result))
352 :     | GREATER => intersect (t1, r2, n, result)
353 :     (* end case *))
354 :     | _ => (n, result)
355 :     (* end case *))
356 :     in
357 :     wrap intersect
358 :     end
359 :     fun intersectWithi mergeFn = let
360 :     fun intersect (t1, t2, n, result) = (case (next t1, next t2)
361 :     of ((T(_, _, xk, x, _), r1), (T(_, _, yk, y, _), r2)) => (
362 :     case Key.compare(xk, yk)
363 :     of LESS => intersect (r1, t2, n, result)
364 :     | EQUAL =>
365 :     intersect (r1, r2, n+1,
366 :     addItem(xk, mergeFn(xk, x, y), result))
367 :     | GREATER => intersect (t1, r2, n, result)
368 :     (* end case *))
369 :     | _ => (n, result)
370 :     (* end case *))
371 :     in
372 :     wrap intersect
373 :     end
374 : jhr 1193
375 :     fun mergeWith mergeFn = let
376 :     fun merge (t1, t2, n, result) = (case (next t1, next t2)
377 :     of ((E, _), (E, _)) => (n, result)
378 :     | ((E, _), (T(_, _, yk, y, _), r2)) =>
379 :     mergef(yk, NONE, SOME y, t1, r2, n, result)
380 :     | ((T(_, _, xk, x, _), r1), (E, _)) =>
381 :     mergef(xk, SOME x, NONE, r1, t2, n, result)
382 :     | ((T(_, _, xk, x, _), r1), (T(_, _, yk, y, _), r2)) => (
383 :     case Key.compare(xk, yk)
384 :     of LESS => mergef(xk, SOME x, NONE, r1, t2, n, result)
385 :     | EQUAL => mergef(xk, SOME x, SOME y, r1, r2, n, result)
386 :     | GREATER => mergef(yk, NONE, SOME y, t1, r2, n, result)
387 :     (* end case *))
388 :     (* end case *))
389 :     and mergef (k, x1, x2, r1, r2, n, result) = (case mergeFn(x1, x2)
390 :     of NONE => merge (r1, r2, n, result)
391 :     | SOME y => merge (r1, r2, n+1, addItem(k, y, result))
392 :     (* end case *))
393 :     in
394 :     wrap merge
395 :     end
396 :     fun mergeWithi mergeFn = let
397 :     fun merge (t1, t2, n, result) = (case (next t1, next t2)
398 :     of ((E, _), (E, _)) => (n, result)
399 :     | ((E, _), (T(_, _, yk, y, _), r2)) =>
400 :     mergef(yk, NONE, SOME y, t1, r2, n, result)
401 :     | ((T(_, _, xk, x, _), r1), (E, _)) =>
402 :     mergef(xk, SOME x, NONE, r1, t2, n, result)
403 :     | ((T(_, _, xk, x, _), r1), (T(_, _, yk, y, _), r2)) => (
404 :     case Key.compare(xk, yk)
405 :     of LESS => mergef(xk, SOME x, NONE, r1, t2, n, result)
406 :     | EQUAL => mergef(xk, SOME x, SOME y, r1, r2, n, result)
407 :     | GREATER => mergef(yk, NONE, SOME y, t1, r2, n, result)
408 :     (* end case *))
409 :     (* end case *))
410 :     and mergef (k, x1, x2, r1, r2, n, result) = (case mergeFn(k, x1, x2)
411 :     of NONE => merge (r1, r2, n, result)
412 :     | SOME y => merge (r1, r2, n+1, addItem(k, y, result))
413 :     (* end case *))
414 :     in
415 :     wrap merge
416 :     end
417 : monnier 467 end (* local *)
418 :    
419 :     fun app f = let
420 :     fun appf E = ()
421 :     | appf (T(_, a, _, x, b)) = (appf a; f x; appf b)
422 :     in
423 :     fn (MAP(_, m)) => appf m
424 :     end
425 :     fun appi f = let
426 :     fun appf E = ()
427 :     | appf (T(_, a, xk, x, b)) = (appf a; f(xk, x); appf b)
428 :     in
429 :     fn (MAP(_, m)) => appf m
430 :     end
431 :    
432 :     fun map f = let
433 :     fun mapf E = E
434 :     | mapf (T(color, a, xk, x, b)) =
435 :     T(color, mapf a, xk, f x, mapf b)
436 :     in
437 :     fn (MAP(n, m)) => MAP(n, mapf m)
438 :     end
439 :     fun mapi f = let
440 :     fun mapf E = E
441 :     | mapf (T(color, a, xk, x, b)) =
442 :     T(color, mapf a, xk, f(xk, x), mapf b)
443 :     in
444 :     fn (MAP(n, m)) => MAP(n, mapf m)
445 :     end
446 :    
447 :     (* Filter out those elements of the map that do not satisfy the
448 :     * predicate. The filtering is done in increasing map order.
449 :     *)
450 :     fun filter pred (MAP(_, t)) = let
451 :     fun walk (E, n, result) = (n, result)
452 :     | walk (T(_, a, xk, x, b), n, result) = let
453 :     val (n, result) = walk(a, n, result)
454 :     in
455 :     if (pred x)
456 :     then walk(b, n+1, addItem(xk, x, result))
457 :     else walk(b, n, result)
458 :     end
459 :     val (n, result) = walk (t, 0, ZERO)
460 :     in
461 :     MAP(n, linkAll result)
462 :     end
463 :     fun filteri pred (MAP(_, t)) = let
464 :     fun walk (E, n, result) = (n, result)
465 :     | walk (T(_, a, xk, x, b), n, result) = let
466 :     val (n, result) = walk(a, n, result)
467 :     in
468 :     if (pred(xk, x))
469 :     then walk(b, n+1, addItem(xk, x, result))
470 :     else walk(b, n, result)
471 :     end
472 :     val (n, result) = walk (t, 0, ZERO)
473 :     in
474 :     MAP(n, linkAll result)
475 :     end
476 :    
477 :     (* map a partial function over the elements of a map in increasing
478 :     * map order.
479 :     *)
480 :     fun mapPartial f = let
481 :     fun f' (xk, x, m) = (case f x
482 :     of NONE => m
483 :     | (SOME y) => insert(m, xk, y)
484 :     (* end case *))
485 :     in
486 :     foldli f' empty
487 :     end
488 :     fun mapPartiali f = let
489 :     fun f' (xk, x, m) = (case f(xk, x)
490 :     of NONE => m
491 :     | (SOME y) => insert(m, xk, y)
492 :     (* end case *))
493 :     in
494 :     foldli f' empty
495 :     end
496 :    
497 :     end;

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0