| Home | Libraries | People | FAQ | More

### 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.