Scheme 48 Manual -- Sets over finite types

Scheme 48 Manual | Contents | In Chapter: Libraries
Previous: Sets over finite types | Next: Sets over finite types

Sets over finite types

The structure enum-sets has a macro for defining types for sets of elements of finite types. These work naturally with the finite types defined by the finite-types structure, but are not tied to them. The syntax for defining such a type is:

(define-enum-set-type id type-name predicate constructor
   element-syntax element-predicate all-elements element-index-ref)

This defines id to be syntax for constructing sets, type-name to be a value representing the type, predicate to be a predicate for those sets, and constructor a procedure for constructing one from a list.

Element-syntax must be the name of a macro for constructing set elements from names (akin to the tag argument to define-enumerated-type). Element-predicate must be a predicate for the element type, all-elements a vector of all values of the element type, and element-index-ref must return the index of an element within the all-elements vector.

(enum-set->list enum-set) -> list
(enum-set-member? enum-set enumerand) -> boolean
(enum-set=? enum-set enum-set) -> boolean
(enum-set-union enum-set enum-set) -> enum-set
(enum-set-intersection enum-set enum-set) -> enum-set
(enum-set-negation enum-set) -> enum-set

Enum-set->list converts a set into a list of its elements. Enum-set-member? tests for membership. Enum-set=? tests two sets of equal type for equality. (If its arguments are not of the same type, enum-set=? raises an exception.) Enum-set-union computes the union of two sets of equal type, enum-set-intersection computes the intersection, and enum-set-negation computes the complement of a set.

Here is an example. Given an enumerated type:

(define-enumerated-type color :color
  color?
  colors
  color-name
  color-index
  (red blue green))

we can define sets of colors:

(define-enum-set-type color-set :color-set
                      color-set?
                      make-color-set
  color color? colors color-index)

> (enum-set->list (color-set red blue))
(#Color red #Color blue)
> (enum-set->list (enum-set-negation (color-set red blue)))
(#Color green)
> (enum-set-member? (color-set red blue) (color blue))
#t

Previous: Sets over finite types | Next: Sets over finite types