Quantifiers: Maps of Numbers

Subtraction on Quantifiers

With Sets and Collectors the semantics of operator - is that of set difference which means, that you can only subtract what has been put into the container before. With Quantifiers that count or quantify their key values in some way, the semantics of operator - may be different.

The question is how subtraction should be defined here?

//Pseudocode:
icl::map<int,some_number> q = {(1->1)};
q -= (2->1);

If type some_number is unsigned a set difference kind of subtraction make sense

icl::map<int,some_number> q = {(1->1)};
q -= (2->1);   // key 2 is not in the map so  
q == {(1->1)}; // q is unchanged by 'aggregate on collision'

If some_number is a signed numerical type the result can also be this

icl::map<int,some_number> q = {(1->1)};
q -= (2->1);             // subtracting works like  
q == {(1->1), (2-> -1)}; // adding the inverse element

As commented in the example, subtraction of a key value pair (k,v) can obviously be defined as adding the inverse element for that key (k,-v), if the key is not yet stored in the map.

Partial and Total Quantifiers and Infinite Vectors

Another concept, that we can think of, is that in a Quantifier every key_value is initially quantified 0-times, where 0 stands for the neutral element of the numeric CodomainT type. Such a Quantifier would be totally defined on all values of it's DomainT type and can be conceived as an InfiniteVector.

To create an infinite vector that is totally defined on it's domain we can set the map's Trait parameter to the value total_absorber. The total_absorber trait fits specifically well with a Quantifier if it's CodomainT has an inverse element, like all signed numerical type have. As we can see later in this section this kind of a total Quantifier has the basic properties that elements of a vector space do provide.

Intersection on Quantifiers

Another difference between Collectors and Quantifiers is the semantics of operator &, that has the meaning of set intersection for Collectors.

For the aggregate on overlap principle the operation & has to be passed to combine associated values on overlap of intervals or collision of keys. This can not be done for Quantifiers, since numeric types do not implement intersection.

For CodomainT types that are not models of Sets operator & is defined as aggregation on the intersection of the domains. Instead of the codomain_intersect functor codomain_combine is used as aggregation operation:

//Pseudocode example for partial Quantifiers p, q:
interval_map<int,int> p, q;
p     = {[1     3)->1   };
q     = {   ([2    4)->1};
p & q =={    [2 3)->2   };

So an addition or aggregation of associated values is done like for operator + but value pairs that have no common keys are not added to the result.

For a Quantifier that is a model of an InfiniteVector and which is therefore defined for every key value of the DomainT type, this definition of operator & degenerates to the same sematics that operaotor + implements:

//Pseudocode example for total Quantifiers p, q:
interval_map<int,int> p, q;
p   = {[min   1)[1      3)[3         max]};
          ->0      ->1         ->0
q   = {[min        2)[2      4)[4    max]};
            ->0         ->1       ->0
p&q =={[min   1)[1  2)[2 3)[3 4)[4   max]};
          ->0    ->1   ->2  ->1    ->0

Laws for Quantifiers of unsigned Numbers

The semantics of icl Maps of Numbers is different for unsigned or signed numbers. So the sets of laws that are valid for Quantifiers will be different depending on the instantiation of an unsigned or a signed number type as CodomainT parameter.

Again, we are presenting the investigated sets of laws, this time for Quantifier types Q which are icl::map<D,N,T>, interval_map<D,N,T> and split_interval_map<D,N,T> where CodomainT type N is a Number and Trait type T is one of the icl's map traits.

Associativity<Q,+,== >: Q a,b,c; a+(b+c) == (a+b)+c
Neutrality<Q,+,== >   : Q a;       a+Q() == a
Commutativity<Q,+,== >: Q a,b;       a+b == b+a

Associativity<Q,&,== >: Q a,b,c; a&(b&c) ==(a&b)&c
Commutativity<Q,&,== >: Q a,b;       a&b == b&a

RightNeutrality<Q,-,== >: Q a;   a-Q() ==  a
Inversion<Q,-,=v= >     : Q a;   a - a =v= Q()

For an unsigned Quantifier, an icl Map of unsigned numbers, the same basic laws apply that are valid for Collectors:

                               +    &    -
Associativity                  ==   ==
Neutrality                     ==        ==
Commutativity                  ==   ==
Inversion absorbs_identities             ==
          enriches_identities            =d=

The subset of laws, that relates to operator + and the neutral element Q() is that of a commutative monoid. This is the same concept, that applies for the CodomainT type. This gives rise to the assumption that an icl Map over a CommutativeModoid is again a CommutativeModoid.

Other laws that were valid for Collectors are not valid for an unsigned Quantifier.

Laws for Quantifiers of signed Numbers

For Quantifiers of signed numbers, or signed Quantifiers, the pattern of valid laws is somewhat different:

                               +    &    -
Associativity                  =v=  =v=
Neutrality                     ==        ==
Commutativity                  ==   ==
Inversion absorbs_identities             ==
          enriches_identities            =d=

The differences are tagged as =v= indicating, that the associativity law is not uniquely valid for a single equality relation == as this was the case for Collector and unsigned Quntifier maps.

The differences are these:

                                   +
Associativity         icl::map     ==
                  interval_map     ==
            split_interval_map     =e=

For operator + the associativity on split_interval_maps is only valid with element equality =e=, which is not a big constrained, because only element equality is required.

For operator & the associativity is broken for all maps that are partial absorbers. For total absorbers associativity is valid for element equality. All maps having the identity enricher Trait are associative wrt. lexicographical equality ==.

Associativity                        &
   absorbs_identities && !is_total   false
   absorbs_identities &&  is_total   =e=
   enriches_identities               ==

Note, that all laws that establish a commutative monoid for operator + and identity element Q() are valid for signed Quantifiers. In addition symmetric difference that does not hold for unsigned Qunatifiers is valid for signed Qunatifiers.

SymmetricDifference<Q,== > : Q a,b,c; (a + b) - (a & b) == (a - b) + (b - a)

For a signed TotalQuantifier Qt symmetrical difference degenerates to a trivial form since operator & and operator + become identical

SymmetricDifference<Qt,== > : Qt a,b,c; (a + b) - (a + b) == (a - b) + (b - a) == Qt()

Existence of an Inverse

By now signed Quantifiers Q are commutative monoids with respect to the operator + and the neutral element Q(). If the Quantifier's CodomainT type has an inverse element like e.g. signed numbers do, the CodomainT type is a commutative or abelian group. In this case a signed Quantifier that is also total has an inverse and the following law holds:

InverseElement<Qt,== > : Qt a; (0 - a) + a == 0

Which means that each TotalQuantifier over an abelian group is an abelian group itself.

This also implies that a Quantifier of Quantifiers is again a Quantifiers and a TotalQuantifier of TotalQuantifiers is also a TotalQuantifier.

TotalQuantifiers resemble the notion of a vector space partially. The concept could be completed to a vector space, if a scalar multiplication was added.