Set: Purely Functional Sets

by Dave Herman (dherman at ccs dot neu dot edu)

This library provides two implementations of functional sets backed by hash tables: one comparing elements for equality using equal?, the other using eq?.

The data structures of this library are immutable. They are implemented on top of PLT Scheme’s immutable hash tables, and therefore should have O(1) running time for extending and O(log n) running time for lookup.

This library was inspired by SRFI-1 and GHC’s Data.Set library.

1 Getting started

The easiest way to use this library is to install its main module, which exports all bindings in the two individual modules:

(require (planet dherman/set:4:0))

Examples:

> (define heroes (list->seteq '(rocky bullwinkle)))

> (define villains (list->seteq '(boris natasha)))

> (for ([x (seteq-union heroes villains)])       (printf "~a~n" x))

rocky   bullwinkle   boris   natasha

2 Sets using equal?

(require (planet dherman/set:4:0/set))

(set? x) → boolean?

x : any

Determines whether x is a set.

(list->set ls) → set?

ls : list?

Produces a set containing the elements in ls. If ls contains duplicates (as determined by equal?), the resulting set contains only the rightmost of the duplicate elements.

(set->list s) → list?

s : set?

Produces a list containing the elements in s. No guarantees are made about the order of the elements in the list.

empty-set : set?

An empty set.

(set-empty? s) → boolean?

s : set?

Determines whether s is empty.

(set-intersection sets ...+) → set?   sets : set?

(set-intersections sets) → set?   sets : (nelistof set?)

Produces the set intersection of sets.

(set-difference sets ...+) → set?   sets : set?

(set-differences sets) → set?   sets : (nelistof set?)

Produces the left-associative set difference of sets.

(set-union sets ...) → set?   sets : set?

(set-unions sets?) → set?   sets? : (listof set?)

Produces the set union of sets.

(set-xor sets ...+) → set?   sets : set?

(set-xors sets) → set?   sets : (nelistof set?)

Produces the exclusive union of sets. This operation is associative and extends to the n-ary case by producing a set of elements that appear in an odd number of sets.

(set-partition sets ...+)   →   set?   set?   sets : set?

(set-partitions sets)   →   set?   set?   sets : (nelistof set?)

Equivalent to

(values (set-differences sets)

(set-intersection (car sets) (unions (cdr sets))))

but implemented more efficiently.

Note that this is not necessarily the same thing as

(values (set-differences sets)

(set-intersections sets)) ; not the same thing!

(set-adjoin s elts ...) → set?

s : set?

elts : any

Produces a set containing the elements of s and elts.

(set-add x s) → set?

x : any

s : set?

Produces a set containing x and the elements of s.

(set-contains? s x) → boolean?

s : set?

x : any

Determines whether the set s contains the element x.

(set-count s) → exact-nonnegative-integer?

s : set?

Produces the number of elements in s.

(for/set (for-clause ...) body ...+)

(for*/set (for-clause ...) body ...+)

Like for/list and for*/list, respectively, but the result is a set. The expressions in the body forms must produce a single value, which is included in the resulting set.

(in-set s) → sequence?

s : set?

Produces a sequence that iterates over the elements of s.

Sets themselves have the prop:sequence property and can therefore be used as sequences.

(set=? s1 s2) → boolean?

s1 : set?

s2 : set?

Determines whether s1 and s2 contain exactly the same elements, using equal? to compare elements.

(subset? s1 s2) → boolean?

s1 : set?

s2 : set?

Determines whether all elements of s1 are contained in s2 (i.e., whether s1 is an improper subset of s2), using equal? to compare elements.

3 Sets using eq?

(require (planet dherman/set:4:0/seteq))

(seteq? x) → boolean?

x : any

Determines whether x is a set.

(list->seteq ls) → seteq?

ls : list?

Produces a set containing the elements in ls. If ls contains duplicates (as determined by eq?), the resulting set contains only the rightmost of the duplicate elements.

(seteq->list s) → list?

s : seteq?

Produces a list containing the elements in s. No guarantees are made about the order of the elements in the list.

empty-seteq : seteq?

An empty set.

(seteq-empty? s) → boolean?

s : seteq?

Determines whether s is empty.

(seteq-intersection sets ...+) → seteq?   sets : seteq?

(seteq-intersections sets) → seteq?   sets : (nelistof seteq?)

Produces the set intersection of sets.

(seteq-difference sets ...+) → seteq?   sets : seteq?

(seteq-differences sets) → seteq?   sets : (nelistof seteq?)

Produces the left-associative set difference of sets.

(seteq-union sets ...) → seteq?   sets : seteq?

(seteq-unions sets?) → seteq?   sets? : (listof seteq?)

Produces the set union of sets.

(seteq-xor sets ...+) → seteq?   sets : seteq?

(seteq-xors sets) → seteq?   sets : (nelistof seteq?)

Produces the exclusive union of sets. This operation is associative and extends to the n-ary case by producing a set of elements that appear in an odd number of sets.

(seteq-partition sets ...+)   →   seteq?   seteq?   sets : seteq?

(seteq-partitions sets)   →   seteq?   seteq?   sets : (nelistof seteq?)

Equivalent to

(values (seteq-differences sets)

(seteq-intersection (car sets) (unions (cdr sets))))

but implemented more efficiently.

Note that this is not necessarily the same thing as

(values (seteq-differences sets)

(seteq-intersections sets)) ; not the same thing!

(seteq-adjoin s elts ...) → seteq?

s : seteq?

elts : any

Produces a set containing the elements of s and elts.

(seteq-add x s) → seteq?

x : any

s : seteq?

Produces a set containing x and the elements of s.

(seteq-contains? s x) → boolean?

s : seteq?

x : any

Determines whether the set s contains the element x.

(seteq-count s) → exact-nonnegative-integer?

s : seteq?

Produces the number of elements in s.

(for/seteq (for-clause ...) body ...+)

(for*/seteq (for-clause ...) body ...+)

Like for/list and for*/list, respectively, but the result is a set. The expressions in the body forms must produce a single value, which is included in the resulting set.

(in-seteq s) → sequence?

s : seteq?

Produces a sequence that iterates over the elements of s.

Sets themselves have the prop:sequence property and can therefore be used as sequences.

(seteq=? s1 s2) → boolean?

s1 : seteq?

s2 : seteq?

Determines whether s1 and s2 contain exactly the same elements, using eq? to compare elements.

(subseteq? s1 s2) → boolean?

s1 : seteq?

s2 : seteq?

Determines whether all elements of s1 are contained in s2 (i.e., whether s1 is an improper subset of s2), using eq? to compare elements.