4.8 Sets

WhizzML has a set datatype, representing a collection of unique, unordered values. WhizzML’s set is implemented as a hash table, and has the associated performance characteristics, including extremely fast insertion and retrieval. The corresponding type predicate is set?:

(set? obj) \(\rightarrow \) boolean

4.8.1 Construction

(set obj1 …) \(\rightarrow \) set
(set* obj1 …list-or-set-args) \(\rightarrow \) set

The first constructor, set, simply constructs a set whose elements are the arguments passed in the call, eliminating any duplicates. When you have a list or a set list-or-set-args and want to add to it several values obj1…, you can use set*.

(set 2 1 3) ;; => #[1 2 3]
(set [1 2] 3) ;; => #[3 [1 2]]
(set* [2 1 3]) ;; => #[1 2 3]
(set* 3 ["a" 2]) ;; => #["a" 3 2]
(set* 3 ["a" 2 3]) ;; => #["a" 3 2]
(set* "a" [1 2] #[true "b" "a"]) ;; => #[true "a" "b" [1 2]]
(list* (set* 1 2 #[3 4])) ;; => [1 4 3 2]

As shown in the examples above, when called with a single list argument, set* becomes WhizzML’s set to list coercion procedure, the dual of list*, but not its inverse because sets preserve neither order nor duplicates:

(list* (set* [2 3 "a"])) ;; => ["a" 3 2]
(list* (set* [3 2 3 "a"])) ;; => ["a" 3 2]

4.8.2 Membership

(add obj set) \(\rightarrow \) set
(remove obj set) \(\rightarrow \) set

Adding and removing single elements to and from sets is accomplished via the standard procedures add and remove, while to check whether a given value belongs to a set one can use the overloaded standard procedure member?:

(add 2 #[]) ;; => #[2]
(add 2 #[1 2]) ;; => #[1 2]
(remove 1 #[1 3]) ;; => #[3]
(remove 1 #["1" 3]) ;; => #["1" 3]
(member? "a" #["a" 2]) ;; => true
(member? 3 #["a" 2]) ;; => false

It is also possible to check for subset relationships using the following predicates:

(subset? set-0 set-1 [strict?]) \(\rightarrow \) boolean
(superset? set-0 set-1 [strict?]) \(\rightarrow \) boolean

The standard predicate subset? (resp. superset?) checks whether its first argument is a subset (resp. superset) of its second one, i.e., whether the second (resp. first) set contains all the elements in the first (resp. second) one, e.g.:

(subset? #[1 true] #[true 2 false 1]) ;; => true
(subset? #[1 true] #[true 2 false]) ;; => false
(subset? a-set a-set) ;; => true
(subset? #[] a-set) ;; => true
(superset? #[true 2 false 1] #[1 true]) ;; => true
(superset? #[true 2 false] #[1 true]) ;; => false
(superset? a-set a-set) ;; => true
(superset? #[] a-set) ;; => false

As shown in the above examples, inclusion checks are non-strict by default, i.e., a set is always a superset and a subset of itself. To check whether the relationship is strict (that is, whether the two subsets are strictly different), set the optional argument strict? to true:

(subset? a-set a-set) ;; => true
(superset? a-set a-set) ;; => true
(subset? a-set a-set false) ;; => true
(superset? a-set a-set false) ;; => true
(subset? a-set a-set true) ;; => false
(superset? a-set a-set true) ;; => false

4.8.3 Set operations

The standard set–theoretical combiners are available for WhizzML sets via the following standard procedures:

(union set-0 set-1) \(\rightarrow \) set
(intersection set-0 set-1) \(\rightarrow \) set
(difference set-0 set-1) \(\rightarrow \) set

union adds all elements of the first set to the second one, intersection returns all elements in both sets and difference removes from list-or-set-0 all elements in list-or-set-1. For instance:

(union #[1 2] #[false 1 4]) ;; => #[false 1 4 2]
(union #[] a-set) ;; => a-set
(intersection #[1 2 "c"] #["c" 2 "b"]) ;; => #[2 "c"]
(intersection a-set #[]) ;; => #[]
(difference #[1 2 3] #[3 1]) ;; => #[2]
(difference #[1 2 3] #["a" false true]) ;; => #[1 2 3]
(difference a-set a-set) ;; => #[]
(difference a-set #[]) ;; => a-set