Examples from Section 3 of Cook's "On Understanding Data Abstraction, Revisited"

gistfile1.sml

(* Interface for sets *)
datatype iset = ISet of unit -> {
  isEmpty: bool,
  contains: int -> bool,
  insert: int -> iset,
  union: iset -> iset }

(* SML's record projection mechanism doesn't work due to the ISet wrapper... *)
val contains = fn (ISet x) => #contains (x ())
val isEmpty = fn (ISet x) => #isEmpty (x ())
val insert = fn (ISet x) => #insert (x ())
val union = fn (ISet x) => #union (x ())

fun Insert (s, n) = 
if contains s n then s else
let fun this () = ISet (fn () => {
  isEmpty = false,
  contains = fn i => i = n orelse contains s i,
  insert = fn i => Insert (this (), i),
  union = fn s => Union (this (), s)
}) in this () end

and Union (s1, s2) = 
if isEmpty s1 then s2 else
if isEmpty s2 then s1 else
let fun this () = ISet (fn () => {
  isEmpty = false,
  contains = fn i => contains s1 i orelse contains s2 i,
  insert = fn i => Insert (this (), i),
  union = fn s => Union (this (), s)
}) in this () end

val EmptySet = 
let fun this () = ISet (fn () => { 
  isEmpty = true,
  contains = fn i => false,
  insert = fn i => Insert (this (), i),
  union = fn s => s
}) in this () end

(* EmptySet.insert(3).union(EmptySet.insert(1)).insert(5).contains(...) *)
val x1 = contains (insert (union (insert EmptySet 3) (insert EmptySet 1)) 5) 1
val x2 = contains (insert (union (insert EmptySet 3) (insert EmptySet 1)) 5) 2
val x3 = contains (insert (union (insert EmptySet 3) (insert EmptySet 1)) 5) 3
val x4 = contains (insert (union (insert EmptySet 3) (insert EmptySet 1)) 5) 4
val x5 = contains (insert (union (insert EmptySet 3) (insert EmptySet 1)) 5) 5