Set:   Purely Functional Sets
1 Getting started
2 Sets using equal?
set?
list->set
set->list
empty-set
set-empty?
set-intersection
set-intersections
set-difference
set-differences
set-union
set-unions
set-xor
set-xors
set-partition
set-partitions
set-adjoin
set-add
set-contains?
set-count
for/  set
for*/  set
in-set
set=?
subset?
3 Sets using eq?
seteq?
list->seteq
seteq->list
empty-seteq
seteq-empty?
seteq-intersection
seteq-intersections
seteq-difference
seteq-differences
seteq-union
seteq-unions
seteq-xor
seteq-xors
seteq-partition
seteq-partitions
seteq-adjoin
seteq-add
seteq-contains?
seteq-count
for/  seteq
for*/  seteq
in-seteq
seteq=?
subseteq?
7.7

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 Racket’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

    2 Sets using equal?

    3 Sets using eq?

1 Getting started

This module provides two libraries, one for equal?-based sets, and one for eq?-based sets.

Examples:
> (define heroes (list->seteq '(rocky bullwinkle)))
> (define villains (list->seteq '(boris natasha)))
> (for ([x (seteq-union heroes villains)])
    (printf "~a~n" x))

boris

rocky

natasha

bullwinkle

2 Sets using equal?

 (require data/set) package: set

procedure

(set? x)  boolean?

  x : any
Determines whether x is a set.

procedure

(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.

procedure

(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.

value

empty-set : set?

An empty set.

procedure

(set-empty? s)  boolean?

  s : set?
Determines whether s is empty.

procedure

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

  sets : set?

procedure

(set-intersections sets)  set?

  sets : (nelistof set?)
Produces the set intersection of sets.

procedure

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

  sets : set?

procedure

(set-differences sets)  set?

  sets : (nelistof set?)
Produces the left-associative set difference of sets.

procedure

(set-union sets ...)  set?

  sets : set?

procedure

(set-unions sets?)  set?

  sets? : (listof set?)
Produces the set union of sets.

procedure

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

  sets : set?

procedure

(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.

procedure

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

procedure

(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!

procedure

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

  s : set?
  elts : any
Produces a set containing the elements of s and elts.

procedure

(set-add x s)  set?

  x : any
  s : set?
Produces a set containing x and the elements of s.

procedure

(set-contains? s x)  boolean?

  s : set?
  x : any
Determines whether the set s contains the element x.

procedure

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

  s : set?
Produces the number of elements in s.

syntax

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

syntax

(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.

procedure

(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.

procedure

(set=? s1 s2)  boolean?

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

procedure

(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 data/seteq) package: set

procedure

(seteq? x)  boolean?

  x : any
Determines whether x is a set.

procedure

(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.

procedure

(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.

An empty set.

procedure

(seteq-empty? s)  boolean?

  s : seteq?
Determines whether s is empty.

procedure

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

  sets : seteq?

procedure

(seteq-intersections sets)  seteq?

  sets : (nelistof seteq?)
Produces the set intersection of sets.

procedure

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

  sets : seteq?

procedure

(seteq-differences sets)  seteq?

  sets : (nelistof seteq?)
Produces the left-associative set difference of sets.

procedure

(seteq-union sets ...)  seteq?

  sets : seteq?

procedure

(seteq-unions sets?)  seteq?

  sets? : (listof seteq?)
Produces the set union of sets.

procedure

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

  sets : seteq?

procedure

(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.

procedure

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

procedure

(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!

procedure

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

  s : seteq?
  elts : any
Produces a set containing the elements of s and elts.

procedure

(seteq-add x s)  seteq?

  x : any
  s : seteq?
Produces a set containing x and the elements of s.

procedure

(seteq-contains? s x)  boolean?

  s : seteq?
  x : any
Determines whether the set s contains the element x.

procedure

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

  s : seteq?
Produces the number of elements in s.

syntax

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

syntax

(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.

procedure

(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.

procedure

(seteq=? s1 s2)  boolean?

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

procedure

(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.