root/trunk/Library/PrefixMap.fss

Revision 4130, 19.2 KB (checked in by sukyoungryu, 3 months ago)

[disambiguator] Fixed handling getters and setters in ExprDisambiguator?. Fixed libraries and tests using getters.
Line 
1(******************************************************************************
2    Copyright 2009 Sun Microsystems, Inc.,
3    4150 Network Circle, Santa Clara, California 95054, U.S.A.
4    All rights reserved.
5
6    U.S. Government Rights - Commercial software.
7    Government users are subject to the Sun Microsystems, Inc. standard
8    license agreement and applicable provisions of the FAR and its supplements.
9
10    Use is subject to license terms.
11
12    This distribution may include materials developed by third parties.
13
14    Sun, Sun Microsystems, the Sun logo and Java are trademarks or registered
15    trademarks of Sun Microsystems, Inc. in the U.S. and other countries.
16 ******************************************************************************)
17
18(******************************************************************************
19
20  Prefix trees, aka Tries: implementing Maps; purely functional
21
22  PrefixMap[\E,F,V\] is the type of maps, indexed by F, and valued in V. Here F is a zero-indexed data type storing elements of type E, supporting an operator addLeft.
23
24  At present F must be a subtype of List[\E\] (where List is defined as in List.fss).
25
26  Future improvements:
27
28   - When the standard collection trait hierarchy is done, we can make this code work more pleasantly and in more generality:
29       - we want F to be any type modelling List[\E\]
30       - we could demand that PrefixMap[\E,F,V\] model Map[\F,V\].
31       - we could vary the indexing data structure for each node. For some prefix trees, it would be best to implement their children as an array. If we are indexing by lists of booleans, we would want an ad-hoc indexing structure whose lookup algorithm is an "if".
32
33 ******************************************************************************)
34
35component PrefixMap
36import List.{...}
37import Map.{...} except { opr BIG UNION, opr BIG UPLUS }
38import PrefixSet.{...}
39import CovariantCollection.{...}
40export PrefixMap
41
42
43trait PrefixMap[\E extends StandardTotalOrder[\E\], F extends List[\E\], V\]
44        extends { Generator[\(F,V)\], Equality[\PrefixMap[\E,F,V\]\] }
45
46    getter asString():String = "{/" (", ".join[\String\](self.map[\String\](fn(x:F,v:V) => (x.asString || " |-> " || v.asString)))) || "/}"
47
48    getter isEmpty():Boolean = (NOT isMember()) AND children().isEmpty
49    getter size():ZZ32
50    content():Maybe[\V\]
51    children():Map[\E,PrefixMap[\E,F,V\]\]
52    isMember():Boolean = (if x <- content() then true else false end)
53    opr |self|:ZZ32 = self.size
54
55    prefixGenerate[\R\](prefix:F, r:Reduction[\R\], body: (F,V)->R):R = do
56        t:R = children().generate[\R\](r, fn (k,v) => v.prefixGenerate[\R\](prefix.addRight(k),r,body))
57        if x <- content() then
58            r.join(body(prefix,x), t)
59        else
60            t
61        end
62    end
63    generate[\R\](r: Reduction[\R\], body:(F,V)->R):R = prefixGenerate[\R\](<|[\E\] |>, r, body)
64
65
66    prefixSeqgen[\R\](prefix:F, r: Reduction[\R\], body: (F,V)->R):R = do
67        t:R = children().seqgen[\R\](r, fn (k,v) => v.prefixSeqgen[\R\](prefix.addRight(k),r,body))
68        if x <- content() then
69            r.join(body(prefix,x),t)
70        else
71            t
72        end
73    end
74    seqgen[\R\](r: Reduction[\R\], body: (F,V)->R):R = prefixSeqgen[\R\](<|[\E\] |>, r, body)
75    seq(self):SequentialGenerator[\(F,V)\] = SeqPrefixMapGenerator[\E,F,V\](self)
76
77
78    dom(self):PrefixSet[\E,F\] = fastPrefixSet[\E,F\](content().holds, children().mapFilter[\PrefixSet[\E,F\]\](fn (k,v) => v.dom()))
79
80
81    opr [k:F]:V throws NotFound = do
82        if x <- member(k) then x else throw NotFound end
83    end
84
85    member(k:F): Maybe[\V\] = do
86        if (h,t) <- k.extractLeft() then
87            if m <- children().member(h) then
88                m.member(t)
89            else
90                Nothing[\V\]
91            end
92        elif x <- content() then
93            Just[\V\](x)
94        else
95            Nothing[\V\]
96        end
97    end
98
99    (** The two-argument version of member returns the default value v
100        if the key is absent from the map. **)
101    member(k:F, v:V): V = do
102        if x <- member(k) then x else v end
103    end
104
105
106    (** minimum and maximum refer to the key **)
107
108    minimum():Maybe[\(F,V)\] = if self.isEmpty then Nothing[\(F,V)\] else Just[\(F,V)\](getMinimum()) end
109    getMinimum():(F,V) throws NotFound = do
110        if x <- content() then
111            (<|[\E\] |>, x)
112        elif (k,v) <- children().minimum() then
113            (f,w) = v.getMinimum()
114            (f.addLeft(k), w)
115        else
116            throw NotFound
117        end
118    end
119
120    maximum(): Maybe[\(F,V)\] = if self.isEmpty then Nothing[\(F,V)\] else Just[\(F,V)\](getMaximum()) end
121    getMaximum():F throws NotFound = do
122        if (k,v) <- children().maximum() then
123            (f,w) = v.getMaximum()
124            (f.addLeft(k), w)
125        elif x <- content() then
126            (<|[\E\] |>, x)
127        else
128            throw NotFound
129        end
130    end
131
132
133    deleteMinimum():PrefixMap[\E,F,V\] =
134            if (_,_,r) <- extractMinimum() then r else self end
135    deleteMaximum():PrefixMap[\E,F,V\] =
136        if (_,_,r) <- extractMaximum() then r else self end
137
138
139    extractMinimum():Maybe[\(F,V, PrefixMap[\E,F,V\])\] = do
140        if x <- content() then
141            Just[\(F, V, PrefixMap[\E,F,V\])\](<|[\E\] |>, x, fastPrefixMap[\E,F,V\](Nothing[\V\], children()))
142        elif (k,v,r) <- children().extractMinimum() then
143            (m,w,s) = v.extractMinimum().get
144            Just[\(F, V, PrefixMap[\E,F,V\])\](m.addLeft(k), w, prefixMap[\E,F,V\](Nothing[\V\], r.add(k,s)))
145        else
146            Nothing[\(F, V, PrefixMap[\E,F,V\])\]
147        end
148    end
149
150    extractMaximum():Maybe[\(F,V, PrefixMap[\E,F,V\])\] = do
151        if (k,v,r) <- children().extractMaximum() then
152            (m,w,s) = v.extractMaximum().get
153            Just[\(F, V, PrefixMap[\E,F,V\])\](m.addLeft(k), w, prefixMap[\E,F,V\](content(), r.add(k,s)))
154        elif x <- content() then
155            Just[\(F, V, PrefixMap[\E,F,V\])\](<|[\E\] |>, x, emptyPrefixMap[\E,F,V\]())
156        else
157            Nothing[\(F, V, PrefixMap[\E,F,V\])\]
158        end
159    end
160
161
162    (** If no mapping presently exists, maps k to v. **)
163    add(x:F,v:V): PrefixMap[\E,F,V\] = do
164        if (h,t) <- x.extractLeft() then
165            f(z:Maybe[\PrefixMap[\E,F,V\]\]):Maybe[\PrefixMap[\E,F,V\]\] = do
166                if s <- z then
167                    Just[\PrefixMap[\E,F,V\]\](s.add(t,v))
168                else
169                    Just(emptyPrefixMap[\E,F,V\]().add(t,v))
170                end
171            end
172            fastPrefixMap[\E,F,V\](content(),children().updateWith(f, h))
173        else
174            if a <- self.isMember() then
175                self
176            else
177                fastPrefixMap[\E,F,V\](Just[\V\](v),children())
178            end
179        end
180    end
181
182    (** Maps k to v. **)
183    update(x:F, v:V):PrefixMap[\E,F,V\] = do
184        if (h,t) <- x.extractLeft() then
185            f(z:Maybe[\PrefixMap[\E,F,V\]\]):Maybe[\PrefixMap[\E,F,V\]\] = do
186                if s <- z then
187                    Just[\PrefixMap[\E,F,V\]\](s.update(t,v))
188                else
189                    Just(emptyPrefixMap[\E,F,V\]().add(t,v))
190                end
191            end
192            prefixMap[\E,F,V\](content(), children().updateWith(f, h))
193        else
194            fastPrefixMap[\E,F,V\](Just[\V\](v),children())
195        end
196    end
197
198    (** Eliminate any mapping for key x. **)
199    delete(x:F): PrefixMap[\E,F,V\] = do
200        if (h,t) <- x.extractLeft() then
201            f(z:Maybe[\PrefixMap[\E,F,V\]\]):Maybe[\PrefixMap[\E,F,V\]\] = do
202                if s <- z then
203                    Just[\PrefixMap[\E,F,V\]\](s.delete(t))
204                else
205                    Nothing[\PrefixMap[\E,F,V\]\]
206                end
207            end
208            prefixMap[\E,F,V\](content(),children().updateWith(f, h))
209        else
210            prefixMap[\E,F,V\](Nothing[\V\],children())
211        end
212    end
213
214    updateWith(f:Maybe[\V\]->Maybe[\V\], k:F):PrefixMap[\E,F,V\] = do
215        if (h,t) <- k.extractLeft() then
216            g(z:Maybe[\PrefixMap[\E,F,V\]\]):Maybe[\PrefixMap[\E,F,V\]\] = do
217                if s <- z then
218                    Just[\PrefixMap[\E,F,V\]\](s.updateWith(g,t))
219                else
220                    if x <- f(Nothing[\V\]) then
221                        Just[\PrefixMap[\E,F,V\]\](emptyPrefixMap[\E,F,V\]().add(t))
222                    else
223                        Nothing[\PrefixMap[\E,F,V\]\]
224                    end
225                end
226            end
227            prefixMap[\E,F,V\](content(), children().updateWith(g, h))
228        else
229            fastPrefixMap[\E,F,V\](f(content()),children())
230        end
231    end
232
233
234    (** UNION favors the leftmost value when a key occurs in both maps. **)
235    opr UNION(self, other:PrefixMap[\E,F,V\]):PrefixMap[\E,F,V\] = do
236        inOrder(x:Maybe[\V\], y:Maybe[\V\]) = if x.holds then x else y end
237        ifOne(k:E, v:PrefixMap[\E,F,V\]):Maybe[\PrefixMap[\E,F,V\]\] = Just[\PrefixMap[\E,F,V\]\](v)
238        mapOne(a:Map[\E,PrefixMap[\E,F,V\]\]):Map[\E,PrefixMap[\E,F,V\]\] = a
239        ifBoth(k:E, u:PrefixMap[\E,F,V\], v:PrefixMap[\E,F,V\]):Maybe[\PrefixMap[\E,F,V\]\] = Just[\PrefixMap[\E,F,V\]\](u UNION v)
240        fastPrefixMap[\E,F,V\](inOrder(content(),other.content()), children().combine[\PrefixMap[\E,F,V\],PrefixMap[\E,F,V\]\](ifBoth,ifOne,ifOne,mapOne,mapOne,other.children()))
241    end
242
243    (** UPLUS (disjoint union) throws the KeyOverlap exception when a key
244            occurs in both maps. **)
245    opr UPLUS(self, other: PrefixMap[\E,F,V\]): PrefixMap[\E,F,V\] = do
246        oneOrOther(x:Maybe[\V\], y:Maybe[\V\]):Maybe[\V\] = if x.holds then if y.holds then throw KeyOverlap else x end else y end
247        ifOne(k:E, v:PrefixMap[\E,F,V\]):Maybe[\PrefixMap[\E,F,V\]\] = Just[\PrefixMap[\E,F,V\]\](v)
248        mapOne(a:Map[\E,PrefixMap[\E,F,V\]\]):Map[\E,PrefixMap[\E,F,V\]\] = a
249        ifBoth(k:E, u:PrefixMap[\E,F,V\], v:PrefixMap[\E,F,V\]):Maybe[\PrefixMap[\E,F,V\]\] = Just[\PrefixMap[\E,F,V\]\](u UPLUS v)
250        fastPrefixMap[\E,F,V\](oneOrOther(content(),other.content()), children().combine[\PrefixMap[\E,F,V\],PrefixMap[\E,F,V\]\](ifBoth,ifOne,ifOne,mapOne,mapOne,other.children()))
251    end
252
253    union(f:(F,V,V)->V, other: PrefixMap[\E,F,V\]): PrefixMap[\E,F,V\] = do
254        innerunion(prefix:F, x:PrefixMap[\E,F,V\], y:PrefixMap[\E,F,V\]):PrefixMap[\E,F,V\] = do
255            ifOne(k:E, v:PrefixMap[\E,F,V\]):Maybe[\PrefixMap[\E,F,V\]\] = Just[\PrefixMap[\E,F,V\]\](v)
256            mapOne(a:Map[\E,PrefixMap[\E,F,V\]\]):Map[\E,PrefixMap[\E,F,V\]\] = a
257            ifBoth(k:E, u:PrefixMap[\E,F,V\], v:PrefixMap[\E,F,V\]):Maybe[\PrefixMap[\E,F,V\]\] = Just[\PrefixMap[\E,F,V\]\](innerunion(prefix.addRight(k),u,v))
258            fastPrefixMap[\E,F,V\](f(prefix,x.content(),y.content()), x.children().combine[\PrefixMap[\E,F,V\],PrefixMap[\E,F,V\]\](ifBoth,ifOne,ifOne,mapOne,mapOne,y.children()))
259        end
260        innerunion(<|[\E\] |>, other)
261    end
262
263
264    splitAt(k:F):(PrefixMap[\E,F,V\],Maybe[\V\],PrefixMap[\E,F,V\]) = do
265        if (h,t) <- k.extractLeft() then
266            (l,x,r) = children().splitAt(h)
267            if m <- x then
268                (ml,mm,mr) = m.splitAt(t)
269                (fastPrefixMap[\E,F,V\](content(), l.add(h,ml)), mm, fastPrefixMap[\E,F,V\](false, r.add(h,mr)))
270            else
271                (fastPrefixMap[\E,F,V\](content(), l), Nothing[\V\], fastPrefixMap[\E,F,V\](false, r))
272            end
273        else
274            (emptyPrefixMap[\E,F,V\](), content(), emptyPrefixMap[\E,F,V\]())
275        end
276    end
277
278
279    concat(other:PrefixMap[\E,F,V\]): PrefixMap[\E,F,V\] = do
280        if (leftmaxkey,leftmaxval,left) <- children().extractMaximum() then
281            if (rightminkey,rightminval,right) <- other.children().extractMinimum() then
282                if leftmaxkey<rightminkey then
283                    fastPrefixSet(isMember() OR other.isMember(), children().concat(other.children()))
284                else
285                    fastPrefixSet(isMember() OR other.isMember(), left.concat3(leftmaxkey, leftmaxval.concat(rightminval), right))
286                end
287            else
288                self
289            end
290        else
291            other
292        end
293    end
294
295    concat3(k:F, v:V, other:PrefixMap[\E,F,V\]):PrefixMap[\E,F,V\] = concat(other.add(k,v))
296
297
298    (** combine is the "swiss army knife" combinator on pairs of maps.
299        We call f() on keys present in both input maps;
300        We call doThis on keys present in self but not in that;
301        We call doThat on keys present in that but not in self.
302        When any of these functions returns r=Just[\Result\], the key is mapped
303            to r.get in the result.
304        When any of these functions returns Nothing[\Result\] there is no
305            mapping for the key in the result.
306
307        mapThis(p,m) must be equivalent to
308          m.mapFilter(fn (k,v) => doThis(p||k, v))
309        and mapThat(p,m) must be equivalent to
310          m.mapFilter(fn (k,v) => doThat(p||k, v));
311        they are included because often they can do their jobs without
312        traversing their argument (eg for union and intersection
313        operations we can pass through or discard whole submaps without
314        traversing them).
315     **)
316
317    combine[\V2,R\](doBoth:(F,V,V2)->Maybe[\R\],
318                    doThis:(F,V)->Maybe[\R\],
319                    doThat:(F,V2)->Maybe[\R\],
320                    mapThis:(F,PrefixMap[\E,F,V\])->PrefixMap[\E,F,R\],
321                    mapThat:(F,PrefixMap[\E,F,V2\])->PrefixMap[\E,F,R\],
322                    that: PrefixMap[\E,F,V2\]): PrefixMap[\E,F,R\] = do
323
324        prefixCombine(prefix:F, arg1:PrefixMap[\E,F,V\], arg2:PrefixMap[\E,F,V2\]):PrefixMap[\E,F,R\] = do
325            c = do
326                if x <- arg1.content() then
327                    if y <- arg2.content() then
328                        doBoth(prefix,x,y)
329                    else
330                        doThis(prefix,x)
331                    end
332                else
333                    if y <- arg2.content() then
334                        doThat(prefix,y)
335                    else
336                        Nothing[\R\]
337                    end
338                end
339            end
340
341            ourDoBoth(e:E, m1:PrefixMap[\E,F,V\], m2:PrefixMap[\E,F,V2\]):PrefixMap[\E,F,R\] = prefixCombine(prefix.addRight(e), m1, m2)
342
343            ourDoThis(e:E, m1:PrefixMap[\E,F,V\]):PrefixMap[\E,F,R\] = mapThis(prefix.addRight(e), m1)
344
345            ourDoThat(e:E, m2:PrefixMap[\E,F,V2\]):PrefixMap[\E,F,R\] = mapThat(prefix.addRight(e), m2)
346
347            ourMapThis(m1:PrefixMap[\E,F,V\]):PrefixMap[\E,F,R\] = m1.mapFilter(ourDoThis)
348
349            ourMapThat(m2:PrefixMap[\E,F,V2\]):PrefixMap[\E,F,R\] = m2.mapFilter(ourDoThat)
350
351            prefixMap(c, arg1.children().combine(ourDoBoth, ourDoThis, ourDoThat, ourMapThis, ourMapThat, arg2.children()))
352        end
353
354        prefixCombine(<|[\E\] |>, self, that)
355    end
356
357    (** Easy-to-use version when there is no special doThis or doThat **)
358    combine[\V2,R\](doBoth:(F,V,V2)->Maybe[\R\],
359                   doThis:(F,V)->Maybe[\R\],
360                   doThat:(F,V2)->Maybe[\R\],
361                   that: PrefixMap[\E,F,V2\]): PrefixMap[\E,F,R\] = do
362        adHocMapThis(p,m) = m.mapFilter(fn (k,v) => doThis(p||k, v))
363        adHocMapThat(p,m) = m.mapFilter(fn (k,v) => doThat(p||k, v))
364        combine[\V2,R\](doBoth, doThis, doThat, adHocMapThis, adHocMapThat, that)
365    end
366
367
368    mapFilter[\R\](f:(F,V)->Maybe[\R\]): PrefixMap[\E,F,R\] = do
369        prefixMapFilter(prefix:F, m:PrefixMap[\E,F,V\]):PrefixMap[\E,F,R\] = do
370            if x <- m.content() then
371                prefixMap[\E,F,R\](f(prefix, x), m.children().mapFilter[\PrefixMap[\E,F,R\]\](fn (e,z) => Just[\PrefixMap[\E,F,R\]\](prefixMapFilter(prefix.addRight(e), z))))
372            else
373                prefixMap[\E,F,R\](Nothing[\R\], m.children().mapFilter[\PrefixMap[\E,F,R\]\](fn (e,z) => Just[\PrefixMap[\E,F,R\]\](prefixMapFilter(prefix.addRight(e), z))))
374            end
375        end
376
377        prefixMapFilter(<|[\E\] |>, self)
378    end
379end
380
381
382
383(* A PrefixMap with given content and children: 'unsafe' as it assumes it is not given any useless tree structure *)
384object fastPrefixMap[\E extends StandardTotalOrder[\E\], F extends List[\E\], V\](v:Maybe[\V\],c:Map[\E,PrefixMap[\E,F,V\]\]) extends PrefixMap[\E,F,V\]
385    getter size():ZZ32 = fixedsize
386    fixedsize:ZZ32 = (if v then 1 else 0 end) + (SUM[(k,a) <- c] a.size)
387    content():Maybe[\V\] = v
388    children():Map[\E,PrefixMap[\E,F,V\]\] = c
389end
390
391
392
393(* A PrefixMap with given children: 'safe' as it will remove any useless tree structure *)
394prefixMap[\E extends StandardTotalOrder[\E\], F extends List[\E\], V\](v:Maybe[\V\], c:Map[\E,PrefixMap[\E,F,V\]\]):PrefixMap[\E,F,V\] = fastPrefixMap[\E,F,V\](v, {[\E,PrefixMap[\E,F,V\]\] k |-> l | (k,l)<-c, l.size =/= 0 })
395
396
397
398emptyPrefixMap[\E extends StandardTotalOrder[\E\], F extends List[\E\],V\]():PrefixMap[\E,F,V\] = fastPrefixMap[\E,F,V\](Nothing[\V\],{[\E,PrefixMap[\E,F,V\]\]})
399
400
401
402singletonPrefixMap[\E extends StandardTotalOrder[\E\], F extends List[\E\],V\](x:F,v:V):PrefixMap[\E,F,V\] = do
403    if (h,t) <- x.extractLeft() then
404        prefixMap[\E,F,V\](Nothing[\V\], singleton[\E,PrefixMap[\E,F,V\]\](h,singletonPrefixMap[\E,F,V\](t,v)))
405    else
406        fastPrefixMap[\E,F,V\](Just[\V\](v), {[\E,PrefixMap[\E,F,V\]\]})
407    end
408end
409
410
411
412prefixMap[\E extends StandardTotalOrder[\E\], F extends List[\E\],V\](g:Generator[\(F,V)\]):PrefixMap[\E,F,V\] = g.generate[\PrefixMap[\E,F,V\]\](DisjointPrefixMapUnion[\E,F,V\], singletonPrefixMap[\E,F,V\])
413
414
415opr {/|->[\E extends StandardTotalOrder[\E\], F extends List[\E\],V\] fs:(F,V)... /}:PrefixMap[\E,F,V\] = prefixMap[\E,F,V\](fs)
416
417opr BIG {/|->[\E extends StandardTotalOrder[\E\], F extends List[\E\],V\] g:Generator[\(F,V)\] /}:PrefixMap[\E,F,V\] = prefixMap[\E,F,V\](g)
418
419opr BIG {/|->[\E extends StandardTotalOrder[\E\], F extends List[\E\],V\] /}:Comprehension[\(F,V),PrefixMap[\E,F,V\],AnyCovColl,AnyCovColl\] =
420    covariantCompr[\(F,V),PrefixMap[\E,F,V\]\](fn cc => prefixMap[\E,F,V\](cc.toArray()))
421
422
423
424
425opr BIG UNION[\E extends StandardTotalOrder[\E\], F extends List[\E\],V\]():Comprehension[\PrefixMap[\E,F,V\],PrefixMap[\E,F,V\],Any,Any\] =
426      embiggen[\ PrefixMap[\E,F,V\] \](fn (a,b) => a UNION b, emptyPrefixMap[\E,F,V\]())
427
428opr BIG UNION[\E extends StandardTotalOrder[\E\], F extends List[\E\],V\](g: Generator[\PrefixMap[\E,F,V\]\]):PrefixMap[\E,F,V\] =
429    __bigOperatorSugar[\PrefixMap[\E,F,V\],PrefixMap[\E,F,V\],Any,Any\](BIG UNION[\E,F,V\](), g)
430
431opr BIG UPLUS[\E extends StandardTotalOrder[\E\], F extends List[\E\],V\]():Comprehension[\PrefixMap[\E,F,V\],PrefixMap[\E,F,V\],Any,Any\] =
432    embiggen[\ PrefixMap[\E,F,V\] \](fn (a,b) => a UPLUS b, emptyPrefixMap[\E,F,V\]())
433
434opr BIG UPLUS[\E extends StandardTotalOrder[\E\], F extends List[\E\],V\](g: Generator[\PrefixMap[\E,F,V\]\]):PrefixMap[\E,F,V\] =
435    __bigOperatorSugar[\PrefixMap[\E,F,V\],PrefixMap[\E,F,V\],Any,Any\](BIG UPLUS[\E,F,V\](), g)
436
437
438
439object SeqPrefixMapGenerator[\E extends StandardTotalOrder[\E\], F extends List[\E\],V\](o:PrefixMap[\E,F,V\])
440    extends SequentialGenerator[\(F,V)\]
441    generate[\R\](r: Reduction[\R\], body: (F,V)->R):R = o.seqgen[\R\](r,body)
442end
443
444object DisjointPrefixMapUnion[\E extends StandardTotalOrder[\E\], F extends List[\E\],V\] extends MonoidReduction[\PrefixMap[\E,F,V\]\]
445    getter asString(): String = "Disjoint prefix map union reduction"
446    empty():PrefixMap[\E,F,V\] = emptyPrefixMap[\E,F,V\]()
447    join(a:PrefixMap[\E,F,V\], b:PrefixMap[\E,F,V\]): PrefixMap[\E,F,V\] =
448        a UPLUS b
449end
450
451
452end
Note: See TracBrowser for help on using the browser.