This is a shameless transcription into Scheme of Ocaml’s set module (from here, described here) by Xavier Leroy. There is a GNU license on the Ocaml code and that may limit what you can do with my transcription.

The Scheme expression defines a value set which is a function that takes as its only argument, a function which takes two elements and returns an integer that is negative, 0 or positive depending or their relative order. For such set members x & y, xRy ⇔ f(x, y) ≤ 0. It is necessary that R be a preorder. I.e. xRy & yRz ⇒ xRz and also xRx. The function set returns a list of set tools for sets of such elements as follows:

(apply (lambda (empty empty? mem add singleton remove
   union inter diff compare equal subset iter fold
   for_all exists filter partition cardinal elements
   min_elt max_elt choose split)
  ......
) (set (lambda (i j) (if (< i j) -1 (if (> i j) 1 0)))))
Code situated at the dots can refer to these set primitives. In the following identifiers beginning with s denote sets as processed by these routines.

It took me two days to transcribe the code and two more to weed out enough transcription errors to pacify these too crude test cases. The tests are adapted here for the repository form of Set. I once wrote a less extensive version of b-tree logic and I am glad that I did not have to debug all of the special cases handled in the Ocaml code.

This describes the interface but with some Ocaml jargon. For instance in the entry for add the text elt -> t -> t means that add takes two arguments; the first is an element of the base type elt and the second a set whose type is t of such elements. It returns a value of type t which is a set.

Both the Ocaml code and Scheme code produce immutable sets. For instance the add function returns a new set while the input set remains unchanged. When the set is large most of the storage is shared between the new and old sets.


Here is some code to bind the names at the top level to support interactive debugging. It assumes that t denotes the yield of set. Here is some code to deal with large sets of integers.