Structures

We will implement sets as boolean-valued functions which return true if applied to an element in the set and false otherwise.

structure Set :> Set =
struct
   type ''a set = ''a -> bool
   fun emptyset _ = false
   fun addset (x, s) = fn e => e = x orelse s e
   fun memberset (x, s) = s x
end;

This structure declaration has collected the type and the three functions under the umbrella name, Set. They are given long identifiers which are formed by prefixing the identifier with the name of the structure and a dot.

Set.emptyset : ''a Set.set

Set.addset : ''a * ''a Set.set -> ''a Set.set

Set.memberset : ''a * ''a Set.set -> bool

In order to understand the effect of the signature constraint above one should compare the results with the results obtained when the signature constraint [the ``:> Set'' part] is omitted. We then obtain a structure which has its principal signature and the types for the three functions are as given below.

Set.emptyset : 'a -> bool

Set.addset : ''a * (''a -> bool) -> ''a -> bool

Set.memberset : 'a * ('a -> 'b) -> 'b

These types seem to provide much less information about the intended use of the functions than do the type constraints imposed by using the signature Set. In particular it seems somewhat hard to understand how the Set.memberset function should be used.

There are other candidate signatures for the Set structure which lie `between' the principal signature and the Set signature. One of these is given below.

signature Set =
sig
   type 'a set
   val emptyset : 'a set
   val addset : ''a * ''a set -> ''a set
   val memberset : 'a * 'a set -> bool
end;

This does not seem to be better than the previous Set signature because it fails to require equality types throughout. In so doing it rules out implementations of the Set structure which are allowed by the previous signature and all but forces the use of functions to represent sets.

Exercise (Addicts only.)

Provide a Set structure which matches the signature given above but stores the set elements in a list.

NEXT ·  UP ·  PREVIOUS ·  CONTENTS ·  INDEX