Skip to content

Instantly share code, notes, and snippets.

@robsimmons

robsimmons/gist:06f79e05d422fb832dd3 Secret

Created March 5, 2012 04:59
Download ZIP

Revisions

  1. robsimmons revised this gist Mar 5, 2012. 1 changed file with 13 additions and 14 deletions.
    27 changes: 13 additions & 14 deletions gistfile1.sml
    View file
    Original file line number Diff line number Diff line change
    @@ -1,47 +1,46 @@
    (* Interface for sets *)
    datatype iset = ISet of {
    datatype iset = ISet of unit -> {
    isEmpty: bool,
    contains: int -> bool,
    insert: int -> iset,
    union: iset -> iset
    }
    union: iset -> iset }

    (* SML's record projection mechanism doesn't work due to the ISet wrapper... *)
    val contains = fn (ISet {contains, ...}) => contains
    val isEmpty = fn (ISet {isEmpty, ...}) => isEmpty
    val insert = fn (ISet {insert, ...}) => insert
    val union = fn (ISet {union, ...}) => union
    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 {
    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
    }) in this () end

    and Union (s1, s2) =
    if isEmpty s1 then s2 else
    if isEmpty s2 then s1 else
    let fun this () = ISet {
    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
    }) in this () end

    val EmptySet =
    let fun this () = ISet {
    let fun this () = ISet (fn () => {
    isEmpty = true,
    contains = fn i => false,
    insert = fn i => Insert (this (), i),
    union = fn s => s
    } in this () end
    }) 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
    val x5 = contains (insert (union (insert EmptySet 3) (insert EmptySet 1)) 5) 5
  2. robsimmons revised this gist Mar 5, 2012. 1 changed file with 1 addition and 0 deletions.
    1 change: 1 addition & 0 deletions gistfile1.sml
    View file
    Original file line number Diff line number Diff line change
    @@ -13,6 +13,7 @@ val insert = fn (ISet {insert, ...}) => insert
    val union = fn (ISet {union, ...}) => union

    fun Insert (s, n) =
    if contains s n then s else
    let fun this () = ISet {
    isEmpty = false,
    contains = fn i => i = n orelse contains s i,
  3. @invalid-email-address Anonymous created this gist Mar 5, 2012.
    46 changes: 46 additions & 0 deletions gistfile1.sml
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,46 @@
    (* Interface for sets *)
    datatype iset = ISet of {
    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 {contains, ...}) => contains
    val isEmpty = fn (ISet {isEmpty, ...}) => isEmpty
    val insert = fn (ISet {insert, ...}) => insert
    val union = fn (ISet {union, ...}) => union

    fun Insert (s, n) =
    let fun this () = ISet {
    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 {
    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 {
    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