Next: , Previous: , Up: setomat   [Index]


12.2 FUNCTIONAL COMPLEMENTABLE SETS AND ORDERED SETS AND SETMAPS

This is a higher order library that will based on a programmable set datatype without complement construct a library for doing set operations by taking complement without a universe defined.

This library treat complements without defining a world. Mathematically that leads to nondecidability issues, but if one construct all such sets from factual discrete elements no technical problems will appear. To actually get a set define a world as the underlying set lib and intersect it with the complemented set, that results in the underlying set. Bitsets has lognot and in guile (gmp) manages bitset complements with lognot and the minus sign. One can define complement for bitsets as well with this library but that’s not nessesary the gmp has all the magic for this.

All nessessry set operators are defined with complement feature included The working code is using the fact that every complemented set that is constructed from atoms and set operations can be defined as A ⊔ Bᶜ. This is not unique definition, to make it unique one could specify that B ∖ A = B that is ̧A⊆Bᶜ and this is also what we constrain the complements to be. FOr unordered sets one can assume that Bᶜ=∅. But when the order is importane one need to be more careful and a more complex solution results. Ordering is defined through the ordering of operands in X ∪ Y and X ∩ Y, that is in a serialisation of X op Y, then elements in sets in X comes befor elements if sets in Y. Ordered sets has a well defined order and can can seen as an assoc list e.g. we can consider mapings from key elements to values in which case lookup of mappings is through the ordered list and hence defines a more generalised lookup. complements of an ordered map sets have no map defined for them, any such maps need to be taken from the world at instantiation of a complemented set into that world, or the real sets it is intersecting with.

12.2.1 API

To use this library import (ice-9 set complement).

scm (make-complementable-set ∅ union intersection difference triple equiv? set-size set? make-one)

and the macro scm (make-complementable-set-mac ∅ union intersection difference triple equiv? set-size set? make-one)

results in:

(values #:u  uSS  #:n  nSS  #:c  cS #:+  ⊕SS  #:-  ∖SS
	#:ou uSSo #:on nSSo #:oc cS #:o+ ⊕SSo #:o- ∖SS 
	#:world Ω #:= ≡SS #:< ⊂SS #:<= ⊆SS)

Ω = ∅⊔∅ᶜ == (make-set ∅ ∅) defines the world.

We also export a complement set struct according to ($ <set> set complement), cset?.

12.2.1.1 Input

union          A,B   -> {x|x∈A or  x∈B}               (A∪B)    
intersection   A,B   -> {x|x∈A and x∈B}               (A∩B)
difference     A,B   -> {x|x∈A and x∉B}               (A∖B)
triple         A,B,C -> {x|x∈A and (x∈B or x∉C)}      (A∩(B∪Cᶜ))
∅              the empty set
equiv?         the set equal predicate
set-size       get the size of a set for the underlying set structure
set?           predicate for beeing a set of the underlying set structure
make-one       Map a set to a set and an element to a set with one element

12.2.1.2 Output

#:u     : ∪  - union for complemented sets         0,1,... arguments
#:n     : ∩  - intersection for complemented sets  0,1,... arguments
#:c     : *ᶜ  - set complement                     1 argument
#:-     : ∖  - set difference =  A∩Bᶜ              2 arguments
#:+     : ⊕  - set adition    = (A∖B ∪ B∖A)        0,1,.... arguments
#:world : the world object
#:=     : equality of sets
#:<     : subset of
#:<=    : subset or equal of

#:ou, #:on, #:oc, #:o+, #:o- : ordered versions of it.

12.2.1.3 Theory

For a full solution one need to track orders in the complement channel as well as the non complement channel.

It looks like we must store either A/B or (A/B)c = B u Ac and do this properly.

1) Q = A/B u C/D = Q Qc = (A/B)c n (C/D)c = = (B u Ac) n (D u Cc) = U + Vc, U = B/C u D/A U u Qc = Qc (Q/U)c = Qc => Q/U = Q => stored pair Q,U

2) Q = A/B n C/D = AnC Qc = (A/B)c u (C/D)c = (Ac u B) u (Cc u D) = (B u D) u (AnC)c Qc = U + Vc, U = B u D => stored pair Q,U

3) Q = A/B u (C/D)c = A/B u Cc u D = (A/B u D) u Cc = Q u Cc Qc = C / (ABc u D) = C (Ac u B) n Dc = C(B u Ac) BC / (A+D) = BCAcDc = BCAc CAc /(A+D) = CAcAcDc = CAc BCAc + CAc

4) Q = A/B n (C/D)c = A/B n(D u Cc) = Q=A(D u Cc) Qc = (B u Ac) u (C n Dc) = U + Vc, U = B u C => stored pair Q,U

5 It implements complementable set and setmaps from different underlying vhash datastructures.) Q = (A/B)c u (C/D)c = B u D u (AnC)c AnC / (B u D)

6) Q = (A/B)c n (C/D)c = (B u Ac) n (C u Dc) = .. It implements complementable set and setmaps from different underlying vhash datastructures.as before


Next: , Previous: , Up: setomat   [Index]