Skip to content

Instantly share code, notes, and snippets.

@robsimmons
Created March 5, 2012 04:59
Show Gist options
  • Save robsimmons/06f79e05d422fb832dd3 to your computer and use it in GitHub Desktop.
Save robsimmons/06f79e05d422fb832dd3 to your computer and use it in GitHub Desktop.
Examples from Section 3 of Cook's "On Understanding Data Abstraction, Revisited"
(* 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment