Next: , Up: setomat   [Index]


12.1 the-ordered-set

This takes an assoc like library and transforms it to an ordered/undordered set and setmap. There is a small change to the setup from scheme’s assoc e.g. the key value pair is not explicit in stead we assume the form (acons kv a).

So consider every set constructed from a union if singletons, if an element is ordered, then they are guarrantead to be reproduced as they appear in the ordered list of union operations with a first come first defined principle. in a difference the oredered list remains but with the removed elements sieved out. This is as well for intersection. elements kan be key value pairs or just a key part, generally there is a poperty of beeing a value, a key value pair may be considered as having the value property but may be configured to not be a value. a value will be used in an assoc manner the value used is the first value that appears in the sequence of operations: unification or intersection, one can for example take an ordered set of non key-values and intersect on a key value set, then the resulting set/map will have the same order of the elements as in the non-value set, but have the values in the key-value set. We construct both a order perserving operations and non order preserving sets in order to be able to make a more effective set operation.

It is a higher order library, it takes a set of functions and construct set opaerations, amongst defined are, ∪,∩,∖,≡,⊕, ordered and unordered.

12.1.1 API

You can reach this code by importing (ice-9 set set)

scm (make-set-from-assoc-mac ...) the macro version of the below

scm (make-set-from-assoc null assoc acons delete hash mk-kv mk-kv kv? kv-key kv-val size value? order? equal? ar->l l->ar)

12.1.1.1 Input

null    =  the empty assoc/set
assoc   =  (assoc x set/map),  maps to either a key value pair or x itself if x is a member of set, else @code{#f}
acons   =  (acons x set/map),  funcitonally add x to set/map
delete  =  (delete x set/map), functionally delete x from set/map
size    =  (size set/map)    , >= the number of elements, if deleted elements conses a delete operation to the assoc then this is greater then the number of elements in the set element operations

mk-kv   = (mk-kv x), makes an element from a normal scheme value  
kv?     = check for a key value structure
kv-key  = key accessor
kv-val  = value accessor
hash    = (hash x hashsize), creates a hash value from the kv element
value?  = if this kv is a key-value pair and the order of the kv pairs in set operations are important
order?  = if the element's construction order is reflected by the set and maintaind through the ordering of the set
equal?  = (equal? x y) the equality predicate used for the kv elements.
ar->l   = the identity map TODO remove this from the api
l->ar   = the identity map TODO remove this from the api

12.1.1.2 Output

The outputs are a value list according to

(values #:=   ≡  #:u   u  #:n   n  #:-  s- #:+  s+ #:<   ⊂ #:<=   ⊆
	#:o=  o≡ #:ou  ou #:on  on #:o- o- #:o+ o+ #:o< o⊂ #:o<= o⊆
	#:n- tripple
        #:fold fold #:map map #:for-each for-each #:empty ∅
	#:set->list   set->list   #:set->assoc set->assoc 
	#:set->kvlist set->kvlist #:make-one make-one)


#:=           :   set identity
#:u           :   set union
#:n           :   set intersection
#:-           :   set difference
#:+           :   set plus
#:<           :   subset of
#:<=          :   subset or equal of
#:o=          :   ordered set identity
#:ou          :   ordered set union
#:on          :   ordered set intersection
#:o-          :   ordered set difference
#:o+          :   ordered set plus
#:o<          :   ordered subset of
#:o<=         :   ordered subset or equal of
#:n-          :   the tripple(a,b,c) =  (a n c) u (a / d)
#:fold        :   (fold f seed set), f : (f kv seed) => new-seed
#:map         :   (map f set), conses the value of f : (f kv) to a list. 
#:for-each    :   (for-each f set), executes f : (f kv) in the set order 
#:empty       :   The empty set
#:set->list   :   Creates a list from the set/map   
#:set->assoc  :   Creates an assoc of the k-v pairs from the set/map
#:set->kvlist :   Crates a list of the kv structures from the set/map
#:make-one    :   Maps a set or one element to a set

Next: , Up: setomat   [Index]