The Set structure

Synopsis

signature SET
structure Set :> SET

A structure of sets and operations on them. The sets are finite and homogeneous, i.e. all its elements have the same type. The implementation is based on lists and too simple to be used for big sets.

Interface

type 'a t
val empty : 'a t
val add : ''a -> ''a t -> ''a t
val Union : ''a t list -> ''a t
val difference : ''a t -> ''a t -> ''a t
val drop : ''a -> ''a t -> ''a t
val equal : ''a t -> ''a t -> bool
val intersects : ''a t -> ''a t -> bool
val list : 'a t -> 'a list
val map : ('a -> ''b) -> 'a t -> ''b t
val member : ''a -> ''a t -> bool
val mk : ''a list -> ''a t
val select : 'a t -> ('a -> bool) -> 'a t
val size : 'a t -> int
val singleton : 'a -> 'a t
val subset : ''a t -> ''a t -> bool
val union : ''a t -> ''a t -> ''a t

Description

type 'a t
the type of finite sets of objects of type 'a.

empty
the empty set.

add e s
returns the set obtained from s by adding element e.

Union l
returns the set obtained by the union of all sets in the list l.

difference s1 s2
returns the set obtained from s1 by removing all members that are members of s2.

drop e s
returns the set obtained from s by removing e.

equal s1 s2
returns true if s1 and s2 have the same members, false otherwise.

intersects s1 s2
returns true if s1 and s2 have a member in common, false otherwise.

list s
returns a list containing all members of s.

map f s
returns the set obtained from s by applying the function f to its members.

member e s
returns true if e is a member of s.

mk l
returns a set that contains each element on the list l as a member.

select s f
returns the set whose members are those members of s on which function f returns true.

size s
returns the number of members of s.

singleton e
returns the set whose only member is e.

subset s1 s2
returns true if s1 is a subset of s2.

union s1 s2
returns the set whose members are the members of s1 or s2.