Assignment 2 solutions

[Anthony Cox]

As many of you didn't appear to understand the assignment, and in particular the second part, I have decided to post the solution to the assignment. Please not that this is a partial solution, I am only providing the code for newset and member to illustrate how to create and traverse the set.

(*
Partial Solution to Assignment 2
Anthony Cox -- March 1999
*)

(* Part 1 *)

datatype 'a setType = Set of unit->unit->'a;
exception NOMORE;

fun newset1 listOfItems =
Set (fn () =>
let
val elems = ref listOfItems;
in
fn () =>
if !elems = []
then raise NOMORE
else
let
val firstItem = hd (!elems);
in
elems := tl (!elems);
firstItem
end
end)

fun mknext (Set x) = x ();

fun member x s =
let
val next = mknext (s)
fun test () =
let
val y = next ()
in
if x = y
then true
else test ()
end
in
test () handle NOMORE => false
end

(* Example *)

val s1 = newset1 [1,2,3,4,5];
val next1 = mknext s1;

(* Part 2 *)

(* Adding the extra function call in funSetType is not strictly necessary.
I just did it to mirror the results of part 1. *)

datatype 'a Iterator = Iter of unit->('a * 'a Iterator);
datatype 'a funSetType = fSet of unit->('a Iterator);

fun newset2 listOfItems =
fSet (fn () =>
let
val items = listOfItems;
fun mkset (nil) = Iter (fn () => raise NOMORE)
| mkset (h::t) = Iter (fn () => (h,mkset(t)))
in
(mkset items)
end)

fun mknext2 (fSet x) = x ();
fun member2 x s =
let
val (Iter initial) = mknext2 (s)
fun test (y,Iter next) =
if y = x
then true
else test (next ())
in
test (initial ()) handle NOMORE => false
end

I hope that by providing a solution, I have shed some insight in how to approach the problem. Please note that, with enough effort, you could probably find ways of improving on these solutions... I am presenting them simply to illustrate the basic technique needed in the assignment.

Anthony Cox

[Viet-Trung Luu]

In article <EpKB...@undergrad.math.uwaterloo.ca>,

Anthony Cox <am...@plg.uwaterloo.ca> wrote:
>As many of you didn't appear to understand the assignment, and in particular
>the second part, I have decided to post the solution to the assignment.
>Please not that this is a partial solution, I am only providing the code for
>newset and member to illustrate how to create and traverse the set.
>
>(*
> Partial Solution to Assignment 2
> Anthony Cox -- March 1999
>*)

[...]

Is it just me or will your newset[12] create sets with duplicate
elements? (Okay, I'm lying -- maybe you do something clever with the
other functions, but your iterator certainly seems happy to iterate over
a duplicate element multiple times.)

For example, if I do:

val foo = newset1 [1,1];
val bar = mknext foo;

bar ();
==> Gives me 1.
bar ();
==> Gives me 1.
bar ();
==> Unhandled exception NOMORE.

(Similarly for newset2, but we have to go through more contortions to
actually obtain any values...)

Is this really the correct/desired behaviour?

- Trung

[Gordon V. Cormack]

In article <EpnCK...@undergrad.math.uwaterloo.ca>,

Viet-Trung Luu <vl...@undergrad.math.uwaterloo.ca> wrote:
>
>For example, if I do:
>
>val foo = newset1 [1,1];
>val bar = mknext foo;
>
>bar ();
>==> Gives me 1.
>bar ();
>==> Gives me 1.
>bar ();
>==> Unhandled exception NOMORE.
>
>(Similarly for newset2, but we have to go through more contortions to
>actually obtain any values...)
>
>Is this really the correct/desired behaviour?
>
>- Trung

I told people who asked that they could assume that the parameter to
newset had no duplicates. This is not to say that it is OK to have
duplicates in your sets (it is not) but that you may assume the
precondition that there aren't any duplicates in the list passed to
newset.
--
Gordon V. Cormack CS Dept, University of Waterloo, Canada N2L 3G1
gvco...@uwaterloo.ca http://cormack.uwaterloo.ca/cormack