2 Copyright (c) 2008-2009 Joachim Faulhaber
4 Distributed under the Boost Software License, Version 1.0.
5 (See accompanying file LICENSE_1_0.txt or copy at
6 http://www.boost.org/LICENSE_1_0.txt)
11 ["Beauty is the ultimate defense against complexity] -- [/David Gelernter]
12 [@http://en.wikipedia.org/wiki/David_Gelernter David Gelernter]
14 In the *icl* we follow the notion, that the semantics of a ['*concept*] or
15 ['*abstract data type*] can be expressed by ['*laws*]. We formulate
16 laws over interval containers that can be evaluated for a given
17 instantiation of the variables contained in the law. The following
18 pseudocode gives a shorthand notation of such a law.
21 T a, b; a + b == b + a;
23 This can of course be coded as a proper c++ class template which has
24 been done for the validation of the *icl*. For sake of simplicity
25 we will use pseudocode here.
27 The laws that describe the semantics of the *icl's* class templates
28 were validated using the Law based Test Automaton ['*LaBatea*],
29 a tool that generates instances for the law's variables and then
31 Since the *icl* deals with sets, maps and relations, that are
32 well known objects from mathematics, the laws that we are
33 using are mostly /recycled/ ones. Also some of those laws are grouped
34 in notions like e.g. /orderings/ or /algebras/.
36 [section Orderings and Equivalences]
38 [h4 Lexicographical Ordering and Equality]
40 On all set and map containers of the icl, there is an `operator <`
42 [@http://www.sgi.com/tech/stl/StrictWeakOrdering.html strict weak ordering].
43 [/ (see also [@http://en.wikipedia.org/wiki/Strict_weak_ordering here]).]
44 The semantics of `operator <` is the same as for an stl's
45 [@http://www.sgi.com/tech/stl/SortedAssociativeContainer.html SortedAssociativeContainer],
47 [@http://www.sgi.com/tech/stl/set.html stl::set]
49 [@http://www.sgi.com/tech/stl/map.html stl::map]:
51 Irreflexivity<T,< > : T a; !(a<a)
52 Asymmetry<T,< > : T a,b; a<b implies !(b<a)
53 Transitivity<T,< > : T a,b,c; a<b && b<c implies a<c
56 `Operator <` depends on the icl::container's template parameter
57 `Compare` that implements a ['strict weak ordering] for the container's
59 For a given `Compare` ordering, `operator <` implements a
60 lexicographical comparison on icl::containers, that uses the
61 `Compare` order to establish a unique sequence of values in
64 The induced equivalence of `operator <` is
65 lexicographical equality
66 which is implemented as `operator ==`.
68 //equivalence induced by strict weak ordering <
69 !(a<b) && !(b<a) implies a == b;
72 follows the semantics of the *stl*.
73 Lexicographical equality is stronger than the equality
74 of elements. Two containers that contain the same elements
75 can be lexicographically unequal, if their elements are
76 differently sorted. Lexicographical comparison belongs to
77 the __bi_iterative__ aspect. Of all the different sequences that are valid
78 for unordered sets and maps, one such sequence is
79 selected by the `Compare` order of elements. Based on
80 this selection a unique iteration is possible.
82 [h4 Subset Ordering and Element Equality]
84 On the __conceptual__ aspect only membership of elements
85 matters, not their sequence. So there are functions
86 `contained_in` and `element_equal` that implement
87 the subset relation and the equality on elements.
88 Yet, `contained_in` and `is_element_equal` functions are not
89 really working on the level of elements. They also
90 work on the basis of the containers templates
91 `Compare` parameter. In practical terms we need to
92 distinguish between lexicographical equality
93 `operator ==` and equality of elements `is_element_equal`,
94 if we work with interval splitting interval containers:
96 split_interval_set<time> w1, w2; //Pseudocode
97 w1 = {[Mon .. Sun)}; //split_interval_set containing a week
98 w2 = {[Mon .. Fri)[Sat .. Sun)}; //Same week split in work and week end parts.
99 w1 == w2; //false: Different segmentation
100 is_element_equal(w1,w2); //true: Same elements contained
103 For a constant `Compare` order on key elements,
104 member function `contained_in` that is defined for all
105 icl::containers implements a
106 [@http://en.wikipedia.org/wiki/Partially_ordered_set partial order]
110 with <= for contained_in,
111 =e= for is_element_equal:
112 Reflexivity<T,<= > : T a; a <= a
113 Antisymmetry<T,<=,=e=> : T a,b; a <= b && b <= a implies a =e= b
114 Transitivity<T,<= > : T a,b,c; a <= b && b <= c implies a <= c
117 The induced equivalence is the equality of elements that
118 is implemented via function `is_element_equal`.
120 //equivalence induced by the partial ordering contained_in on icl::container a,b
121 a.contained_in(b) && b.contained_in(a) implies is_element_equal(a, b);
124 [endsect][/ Orderings and Equivalences]
128 For all set types `S` that are models concept `Set`
129 (__icl_set__, __itv_set__, __sep_itv_set__ and __spl_itv_set__)
130 most of the well known mathematical
131 [@http://en.wikipedia.org/wiki/Algebra_of_sets laws on sets]
132 were successfully checked via LaBatea. The next tables
133 are giving an overview over the checked laws ordered by
134 operations. If possible, the laws are formulated with
135 the stronger lexicographical equality (`operator ==`)
136 which implies the law's validity for the weaker
137 element equality `is_element_equal`. Throughout this
138 chapter we will denote element equality as `=e=` instead
139 of `is_element_equal` where a short notation is advantageous.
141 [h5 Laws on set union]
143 For the operation ['*set union*] available as
144 `operator +, +=, |, |=` and the neutral element
145 `identity_element<S>::value()` which is the empty set `S()`
148 Associativity<S,+,== >: S a,b,c; a+(b+c) == (a+b)+c
149 Neutrality<S,+,== > : S a; a+S() == a
150 Commutativity<S,+,== >: S a,b; a+b == b+a
153 [h5 Laws on set intersection]
155 For the operation ['*set intersection*] available as
156 `operator &, &=` these laws were validated:
159 Associativity<S,&,== >: S a,b,c; a&(b&c) == (a&b)&c
160 Commutativity<S,&,== >: S a,b; a&b == b&a
164 Neutrality has *not* been validated to avoid
165 additional requirements on the sets template
168 [h5 Laws on set difference]
170 For set difference there are only these laws. It is
171 not associative and not commutative. It's neutrality
175 RightNeutrality<S,-,== > : S a; a-S() == a
176 Inversion<S,-,== >: S a; a - a == S()
179 Summarized in the next table are laws that use `+`, `&` and `-`
180 as a single operation. For all validated laws,
181 the left and right hand sides of the equations
182 are lexicographically equal, as denoted by `==` in the cells
193 [h5 Distributivity Laws]
195 Laws, like distributivity, that use more than one operation can
196 sometimes be instantiated for different sequences of operators
197 as can be seen below. In the two instantiations of the distributivity
198 laws operators `+` and `&` are swapped. So we can have small operator
199 signatures like `+,&` and `&,+` to describe such instantiations,
200 which will be used below.
201 Not all instances of distributivity laws hold for lexicographical equality.
202 Therefore they are denoted using a /variable/ equality `=v=` below.
205 Distributivity<S,+,&,=v= > : S a,b,c; a + (b & c) =v= (a + b) & (a + c)
206 Distributivity<S,&,+,=v= > : S a,b,c; a & (b + c) =v= (a & b) + (a & c)
207 RightDistributivity<S,+,-,=v= > : S a,b,c; (a + b) - c =v= (a - c) + (b - c)
208 RightDistributivity<S,&,-,=v= > : S a,b,c; (a & b) - c =v= (a - c) & (b - c)
211 The next table shows the relationship between
213 [link boost_icl.introduction.interval_combining_styles interval combining style]
215 used equality relation.
219 Distributivity joining == ==
224 RightDistributivity joining == ==
229 The table gives an overview over 12 instantiations of
230 the four distributivity laws and shows the equalities
231 which the instantiations holds for. For instance
232 `RightDistributivity` with operator signature `+,-`
233 instantiated for __spl_itv_sets__ holds only for
234 element equality (denoted as `=e=`):
236 RightDistributivity<S,+,-,=e= > : S a,b,c; (a + b) - c =e= (a - c) + (b - c)
238 The remaining five instantiations of `RightDistributivity`
239 are valid for lexicographical equality (demoted as `==`) as well.
241 [link boost_icl.introduction.interval_combining_styles Interval combining styles]
242 correspond to containers according to
246 separating separate_interval_set
247 splitting split_interval_set
251 Finally there are two laws that combine all three major set operations:
252 De Mogans Law and Symmetric Difference.
256 De Morgans Law is better known in an incarnation where the unary
257 complement operation `~` is used. `~(a+b) == ~a * ~b`. The version
258 below is an adaption for the binary set difference `-`, which is
259 also called ['*relative complement*].
261 DeMorgan<S,+,&,=v= > : S a,b,c; a - (b + c) =v= (a - b) & (a - c)
262 DeMorgan<S,&,+,=v= > : S a,b,c; a - (b & c) =v= (a - b) + (a - c)
267 DeMorgan joining == ==
272 Again not all law instances are valid for lexicographical equality.
273 The second instantiations only holds for element equality, if
274 the interval sets are non joining.
276 [h5 Symmetric Difference]
279 SymmetricDifference<S,== > : S a,b,c; (a + b) - (a & b) == (a - b) + (b - a)
282 Finally Symmetric Difference holds for all of icl set types and
283 lexicographical equality.
291 By definition a map is set of pairs. So we would expect maps to
292 obey the same laws that are valid for sets. Yet
293 the semantics of the *icl's* maps may be a different one, because
294 of it's aggregating facilities, where the aggregating combiner
295 operations are passed to combine the map's associated values.
296 It turns out, that the aggregation on overlap principle
297 induces semantic properties to icl maps in such a way,
298 that the set of equations that are valid will depend on
299 the semantics of the type `CodomainT` of the map's associated
302 This is less magical as it might seem at first glance.
303 If, for instance, we instantiate an __itv_map__ to
304 collect and concatenate
305 `std::strings` associated to intervals,
308 interval_map<int,std::string> cat_map;
309 cat_map += make_pair(interval<int>::rightopen(1,5),std::string("Hello"));
310 cat_map += make_pair(interval<int>::rightopen(3,7),std::string(" World"));
311 cout << "cat_map: " << cat_map << endl;
314 we won't be able to apply `operator -=`
316 // This will not compile because string::operator -= is missing.
317 cat_map -= make_pair(interval<int>::rightopen(3,7),std::string(" World"));
319 because, as std::sting does not implement `-=` itself, this won't compile.
320 So all *laws*, that rely on `operator -=` or `-` not only will not be valid they
321 can not even be stated.
322 This reduces the set of laws that can be valid for a richer `CodomainT`
323 type to a smaller set of laws and thus to a less restricted semantics.
325 Currently we have investigated and validated two major instantiations
328 * ['*Maps of Sets*] that will be called ['*Collectors*] and
329 * ['*Maps of Numbers*] which will be called ['*Quantifiers*]
331 both of which seem to have many interesting use cases for practical
332 applications. The semantics associated with the term /Numbers/
334 [@http://en.wikipedia.org/wiki/Monoid commutative monoid]
337 [@http://en.wikipedia.org/wiki/Abelian_group commutative or abelian group]
339 From a practical point of view we can think
340 of numbers as counting or quantifying the key values
343 Icl ['*Maps of Sets*] or ['*Collectors*]
344 are models of concept `Set`. This implies that all laws that have been
345 stated as a semantics for `icl::Sets` in the previous chapter also hold for
347 Icl ['*Maps of Numbers*] or ['*Quantifiers*] on the contrary are not models
349 But there is a substantial intersection of laws that apply both for
350 `Collectors` and `Quantifiers`.
353 [[Kind of Map] [Alias] [Behavior] ]
354 [[Maps of Sets] [Collector] [Collects items *for* key values] ]
355 [[Maps of Numbers][Quantifier][Counts or quantifies *the* key values]]
358 In the next two sections the law based semantics of ['*Collectors*]
359 and ['*Quantifiers*] will be described in more detail.
363 [section Collectors: Maps of Sets]
365 Icl `Collectors`, behave like `Sets`.
366 This can be understood easily, if we consider, that
367 every map of sets can be transformed to an equivalent
369 For instance in the pseudocode below map `m`
371 icl::map<int,set<int> > m = {(1->{1,2}), (2->{1})};
373 is equivalent to set `s`
375 icl::set<pair<int,int> > s = {(1,1),(1,2), //representing 1->{1,2}
376 (2,1) }; //representing 2->{1}
379 Also the results of add, subtract and other operations on `map m` and `set s`
380 preserves the equivalence of the containers ['*almost*] perfectly:
383 m == {(1->{1,2,3}), (2->{1})}; //aggregated on collision of key value 1
385 s == {(1,1),(1,2),(1,3), //representing 1->{1,2,3}
386 (2,1) }; //representing 2->{1}
389 The equivalence of `m` and `s` is only violated if an
390 empty set occurres in `m` by subtraction of a value pair:
393 m == {(1->{1,2,3}), (2->{})}; //aggregated on collision of key value 2
395 s == {(1,1),(1,2),(1,3) //representing 1->{1,2,3}
396 }; //2->{} is not represented in s
399 This problem can be dealt with in two ways.
401 # Deleting value pairs form the Collector, if it's associated value
402 becomes a neutral value or `identity_element`.
403 # Using a different equality, called distinct equality in the laws
404 to validate. Distinct equality only
405 accounts for value pairs that that carry values unequal to the `identity_element`.
407 Solution (1) led to the introduction of map traits, particularly trait
408 ['*partial_absorber*], which is the default setting in all icl's map
411 Solution (2), is applied to check the semantics of icl::Maps for the
412 partial_enricher trait that does not delete value pairs that carry
413 identity elements. Distinct equality is implemented by a non member function
414 called `is_distinct_equal`. Throughout this chapter
415 distinct equality in pseudocode and law denotations is denoted
418 The validity of the sets of laws that make up `Set` semantics
419 should now be quite evident. So the following text shows the
420 laws that are validated for all `Collector` types `C`. Which are
421 __icl_map__`<D,S,T>`, __itv_map__`<D,S,T>` and __spl_itv_map__`<D,S,T>`
422 where `CodomainT` type `S` is a model of `Set` and `Trait` type `T` is either
423 __pabsorber__ or __penricher__.
426 [h5 Laws on set union, set intersection and set difference]
429 Associativity<C,+,== >: C a,b,c; a+(b+c) == (a+b)+c
430 Neutrality<C,+,== > : C a; a+C() == a
431 Commutativity<C,+,== >: C a,b; a+b == b+a
433 Associativity<C,&,== >: C a,b,c; a&(b&c) ==(a&b)&c
434 Commutativity<C,&,== >: C a,b; a&b == b&a
436 RightNeutrality<C,-,== >: C a; a-C() == a
437 Inversion<C,-,=v= > : C a; a - a =v= C()
440 All the fundamental laws could be validated for all
441 icl Maps in their instantiation as Maps of Sets or Collectors.
442 As expected, Inversion only holds for distinct equality,
443 if the map is not a `partial_absorber`.
450 Inversion partial_absorber ==
454 [h5 Distributivity Laws]
457 Distributivity<C,+,&,=v= > : C a,b,c; a + (b & c) =v= (a + b) & (a + c)
458 Distributivity<C,&,+,=v= > : C a,b,c; a & (b + c) =v= (a & b) + (a & c)
459 RightDistributivity<C,+,-,=v= > : C a,b,c; (a + b) - c =v= (a - c) + (b - c)
460 RightDistributivity<C,&,-,=v= > : C a,b,c; (a & b) - c =v= (a - c) & (b - c)
463 Results for the distributivity laws are almost identical to
464 the validation of sets except that
465 for a `partial_enricher map` the law `(a & b) - c == (a - c) & (b - c)`
466 holds for lexicographical equality.
470 Distributivity joining == ==
471 splitting partial_absorber =e= =e=
472 partial_enricher =e= ==
475 RightDistributivity joining == ==
479 [h5 DeMorgan's Law and Symmetric Difference]
482 DeMorgan<C,+,&,=v= > : C a,b,c; a - (b + c) =v= (a - b) & (a - c)
483 DeMorgan<C,&,+,=v= > : C a,b,c; a - (b & c) =v= (a - b) + (a - c)
488 DeMorgan joining == ==
493 SymmetricDifference<C,== > : C a,b,c; (a + b) - (a * b) == (a - b) + (b - a)
496 Reviewing the validity tables above shows, that the sets of valid laws for
497 `icl Sets` and `icl Maps of Sets` that are /identity absorbing/ are exactly the same.
498 As expected, only for Maps of Sets that represent empty sets as associated values,
499 called /identity enrichers/, there are marginal semantic differences.
501 [endsect][/ Collectors]
503 [section Quantifiers: Maps of Numbers]
505 [h5 Subtraction on Quantifiers]
507 With `Sets` and `Collectors` the semantics of
509 that of /set difference/ which means, that you can
510 only subtract what has been put into the container before.
511 With `Quantifiers` that ['*count*] or ['*quantify*]
512 their key values in some way,
513 the semantics of `operator -` may be different.
515 The question is how subtraction should be defined here?
518 icl::map<int,some_number> q = {(1->1)};
521 If type `some_number` is `unsigned` a /set difference/ kind of
522 subtraction make sense
524 icl::map<int,some_number> q = {(1->1)};
525 q -= (2->1); // key 2 is not in the map so
526 q == {(1->1)}; // q is unchanged by 'aggregate on collision'
528 If `some_number` is a `signed` numerical type
529 the result can also be this
531 icl::map<int,some_number> q = {(1->1)};
532 q -= (2->1); // subtracting works like
533 q == {(1->1), (2-> -1)}; // adding the inverse element
535 As commented in the example, subtraction of a key value
536 pair `(k,v)` can obviously be defined as adding the ['*inverse element*]
537 for that key `(k,-v)`, if the key is not yet stored in the map.
539 [h4 Partial and Total Quantifiers and Infinite Vectors]
541 Another concept, that we can think of, is that in a `Quantifier`
542 every `key_value` is initially quantified `0`-times, where `0` stands
543 for the neutral element of the numeric `CodomainT` type.
544 Such a `Quantifier` would be totally defined on all values of
545 it's `DomainT` type and can be
546 conceived as an `InfiniteVector`.
548 To create an infinite vector
549 that is totally defined on it's domain we can set
550 the map's `Trait` parameter to the value __tabsorber__.
551 The __tabsorber__ trait fits specifically well with
552 a `Quantifier` if it's `CodomainT` has an inverse
553 element, like all signed numerical type have.
554 As we can see later in this section this kind of
555 a total `Quantifier` has the basic properties that
557 [@http://en.wikipedia.org/wiki/Vector_space vector space]
561 [h5 Intersection on Quantifiers]
563 Another difference between `Collectors` and `Quantifiers`
564 is the semantics of `operator &`, that has the meaning of
565 set intersection for `Collectors`.
567 For the /aggregate on overlap principle/ the operation `&`
568 has to be passed to combine associated values on overlap
569 of intervals or collision of keys. This can not be done
570 for `Quantifiers`, since numeric types do not implement
573 For `CodomainT` types that are not models of `Sets`
574 `operator & ` is defined as ['aggregation on the intersection
575 of the domains]. Instead of the `codomain_intersect` functor
576 `codomain_combine` is used as aggregation operation:
578 //Pseudocode example for partial Quantifiers p, q:
579 interval_map<int,int> p, q;
582 p & q =={ [2 3)->2 };
584 So an addition or aggregation of associated values is
585 done like for `operator +` but value pairs that have
586 no common keys are not added to the result.
588 For a `Quantifier` that is a model of an `InfiniteVector`
589 and which is therefore defined for every key value of
590 the `DomainT` type, this definition of `operator &`
591 degenerates to the same sematics that `operaotor +`
594 //Pseudocode example for total Quantifiers p, q:
595 interval_map<int,int> p, q;
596 p = {[min 1)[1 3)[3 max]};
598 q = {[min 2)[2 4)[4 max]};
600 p&q =={[min 1)[1 2)[2 3)[3 4)[4 max]};
604 [h4 Laws for Quantifiers of unsigned Numbers]
606 The semantics of icl Maps of Numbers is different
607 for unsigned or signed numbers. So the sets of
608 laws that are valid for Quantifiers will be different
609 depending on the instantiation of an unsigned or
610 a signed number type as `CodomainT` parameter.
612 Again, we are presenting the investigated sets of laws, this time for
613 `Quantifier` types `Q` which are
614 __icl_map__`<D,N,T>`, __itv_map__`<D,N,T>` and __spl_itv_map__`<D,N,T>`
615 where `CodomainT` type `N` is a `Number` and `Trait` type `T` is one of
616 the icl's map traits.
619 Associativity<Q,+,== >: Q a,b,c; a+(b+c) == (a+b)+c
620 Neutrality<Q,+,== > : Q a; a+Q() == a
621 Commutativity<Q,+,== >: Q a,b; a+b == b+a
623 Associativity<Q,&,== >: Q a,b,c; a&(b&c) ==(a&b)&c
624 Commutativity<Q,&,== >: Q a,b; a&b == b&a
626 RightNeutrality<Q,-,== >: Q a; a-Q() == a
627 Inversion<Q,-,=v= > : Q a; a - a =v= Q()
630 For an `unsigned Quantifier`, an icl Map of `unsigned numbers`,
631 the same basic laws apply that are
632 valid for `Collectors`:
639 Inversion absorbs_identities ==
640 enriches_identities =d=
643 The subset of laws, that relates to `operator +` and the neutral
644 element `Q()` is that of a commutative monoid. This is the same
645 concept, that applies for the `CodomainT` type. This gives
646 rise to the assumption that an icl `Map` over a `CommutativeModoid`
647 is again a `CommutativeModoid`.
649 Other laws that were valid for `Collectors` are not valid
650 for an `unsigned Quantifier`.
653 [h4 Laws for Quantifiers of signed Numbers]
655 For `Quantifiers` of signed numbers, or
656 `signed Quantifiers`, the pattern of valid
657 laws is somewhat different:
660 Associativity =v= =v=
663 Inversion absorbs_identities ==
664 enriches_identities =d=
667 The differences are tagged as `=v=` indicating, that
668 the associativity law is not uniquely valid for a single
669 equality relation `==` as this was the case for
670 `Collector` and `unsigned Quntifier` maps.
672 The differences are these:
675 Associativity icl::map ==
677 split_interval_map =e=
679 For `operator +` the associativity on __spl_itv_maps__ is only valid
680 with element equality `=e=`, which is not a big constrained, because
681 only element equality is required.
683 For `operator &` the associativity is broken for all maps
684 that are partial absorbers. For total absorbers associativity
685 is valid for element equality. All maps having the /identity enricher/
686 Trait are associative wrt. lexicographical equality `==`.
689 absorbs_identities && !is_total false
690 absorbs_identities && is_total =e=
691 enriches_identities ==
694 Note, that all laws that establish a commutative
695 monoid for `operator +` and identity element `Q()` are valid
696 for `signed Quantifiers`.
697 In addition symmetric difference that does not
698 hold for `unsigned Qunatifiers` is valid
699 for `signed Qunatifiers`.
702 SymmetricDifference<Q,== > : Q a,b,c; (a + b) - (a & b) == (a - b) + (b - a)
704 For a `signed TotalQuantifier` `Qt` symmetrical difference degenerates to
705 a trivial form since `operator &` and `operator +` become identical
707 SymmetricDifference<Qt,== > : Qt a,b,c; (a + b) - (a + b) == (a - b) + (b - a) == Qt()
710 [h5 Existence of an Inverse]
712 By now `signed Quantifiers` `Q` are
715 `operator +` and the neutral element `Q()`.
716 If the Quantifier's `CodomainT` type has an /inverse element/
717 like e.g. `signed numbers` do,
718 the `CodomainT` type is a
719 ['*commutative*] or ['*abelian group*].
720 In this case a `signed Quantifier` that is also ['*total*]
721 has an ['*inverse*] and the following law holds:
724 InverseElement<Qt,== > : Qt a; (0 - a) + a == 0
727 Which means that each `TotalQuantifier` over an
732 This also implies that a `Quantifier` of `Quantifiers`
733 is again a `Quantifiers` and a
734 `TotalQuantifier` of `TotalQuantifiers`
735 is also a `TotalQuantifier`.
737 `TotalQuantifiers` resemble the notion of a
738 vector space partially.
739 The concept could be completed to a vector space,
740 if a scalar multiplication was added.
741 [endsect][/ Quantifiers]
744 [section Concept Induction]
746 Obviously we can observe the induction of semantics
747 from the `CodomainT` parameter into the instantiations
751 [[] [is model of] [if] [example]]
752 [[`Map<D,Monoid>`] [`Modoid`] [] [`interval_map<int,string>`]]
753 [[`Map<D,Set,Trait>`] [`Set`] [`Trait::absorbs_identities`][`interval_map<int,std::set<int> >`]]
754 [[`Map<D,CommutativeMonoid>`][`CommutativeMonoid`][] [`interval_map<int,unsigned int>`]]
755 [[`Map<D,CommutativeGroup>`] [`CommutativeGroup`] [`Trait::is_total`] [`interval_map<int,int,total_absorber>`]]
758 [endsect][/ Concept Induction]
760 [endsect][/ Semantics]