Collectors: Maps of Sets

| Home | Libraries | People | FAQ | More

### Collectors: Maps of Sets

Icl `Collectors`, behave like `Sets`. This can be understood easily, if we consider, that every map of sets can be transformed to an equivalent set of pairs. For instance in the pseudocode below map `m`

    icl::map<int,set<int> >  m = {(1->{1,2}), (2->{1})};

is equivalent to set `s`

    icl::set<pair<int,int> > s = {(1,1),(1,2),   //representing 1->{1,2}
                                  (2,1)       }; //representing 2->{1}

Also the results of add, subtract and other operations on `map m` and `set s` preserves the equivalence of the containers almost perfectly:

    m += (1,3);
    m == {(1->{1,2,3}), (2->{1})}; //aggregated on collision of key value 1
    s += (1,3);
    s == {(1,1),(1,2),(1,3),   //representing 1->{1,2,3}
          (2,1)             }; //representing 2->{1}

The equivalence of `m` and `s` is only violated if an empty set occurres in `m` by subtraction of a value pair:

    m -= (2,1);
    m == {(1->{1,2,3}), (2->{})}; //aggregated on collision of key value 2
    s -= (2,1);
    s == {(1,1),(1,2),(1,3)   //representing 1->{1,2,3}
                           }; //2->{} is not represented in s

This problem can be dealt with in two ways.

1. Deleting value pairs form the Collector, if it's associated value becomes a neutral value or `identity_element`.
2. Using a different equality, called distinct equality in the laws to validate. Distinct equality only accounts for value pairs that that carry values unequal to the `identity_element`.

Solution (1) led to the introduction of map traits, particularly trait partial_absorber, which is the default setting in all icl's map templates.

Solution (2), is applied to check the semantics of icl::Maps for the partial_enricher trait that does not delete value pairs that carry identity elements. Distinct equality is implemented by a non member function called `is_distinct_equal`. Throughout this chapter distinct equality in pseudocode and law denotations is denoted as `=d=` operator.

The validity of the sets of laws that make up `Set` semantics should now be quite evident. So the following text shows the laws that are validated for all `Collector` types `C`. Which are `icl::map``<D,S,T>`, `interval_map``<D,S,T>` and `split_interval_map``<D,S,T>` where `CodomainT` type `S` is a model of `Set` and `Trait` type `T` is either `partial_absorber` or `partial_enricher`.

###### Laws on set union, set intersection and set difference

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

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

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

All the fundamental laws could be validated for all icl Maps in their instantiation as Maps of Sets or Collectors. As expected, Inversion only holds for distinct equality, if the map is not a `partial_absorber`.

                                 +    &    -
    Associativity                ==   ==
    Neutrality                   ==        ==
    Commutativity                ==   ==
    Inversion partial_absorber             ==
              partial_enricher             =d=

###### Distributivity Laws

         Distributivity<C,+,&,=v= > : C a,b,c; a + (b & c) =v= (a + b) & (a + c)
         Distributivity<C,&,+,=v= > : C a,b,c; a & (b + c) =v= (a & b) + (a & c)
    RightDistributivity<C,+,-,=v= > : C a,b,c; (a + b) - c =v= (a - c) + (b - c)
    RightDistributivity<C,&,-,=v= > : C a,b,c; (a & b) - c =v= (a - c) & (b - c)

Results for the distributivity laws are almost identical to the validation of sets except that for a `partial_enricher map` the law `(a & b) - c == (a - c) & (b - c)` holds for lexicographical equality.

                                                       +,&    &,+
         Distributivity  joining                       ==     ==
                         splitting   partial_absorber  =e=    =e=
                                     partial_enricher  =e=    ==

                                                       +,-    &,-
    RightDistributivity  joining                       ==     ==
                         splitting                     =e=    ==

###### DeMorgan's Law and Symmetric Difference

    DeMorgan<C,+,&,=v= > : C a,b,c; a - (b + c) =v= (a - b) & (a - c)
    DeMorgan<C,&,+,=v= > : C a,b,c; a - (b & c) =v= (a - b) + (a - c)

                             +,&     &,+
    DeMorgan  joining        ==      ==
              splitting      ==      =e=

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

Reviewing the validity tables above shows, that the sets of valid laws for `icl Sets` and `icl Maps of Sets` that are identity absorbing are exactly the same. As expected, only for Maps of Sets that represent empty sets as associated values, called identity enrichers, there are marginal semantic differences.