HW6 - Sequences in ML

Note: this is still under revision. Expect change without notice. Expect to turn in the vector and list implementations first, and the rest later. Feel free to tell me where this needs clarification.

The Basic Idea

The objective of this assignment is to implement a finite sequence datatype in a number of ways, and then package each as a structure all sharing the same signature. Your implementation should be properly commented and indented, and in good ML style - eg no horrible side effects or refs where a simple efficient tail recursive loop would do.

The operations on finite sequences are: finding the length, accessing the n'th element, inserting an element, deleting an element, appending two sequences, chopping a sequence in two, mapping a function over a sequence, and comparing two sequences for equality. These will all be non-destructive, ie they will not change any old sequence only build new ones.

You will implement sequences in five ways:

  1. vector
  2. list
  3. prefix list
  4. binary tree
  5. a more advanced datastructure of your choice (eg balanced binary tree, skip list, list of hunks.)
You will also implement a ``test rig'' for testing implementations of sequences, so you can ensure all your structures meet the requirements.

We will not only grade them, we will also benchmark them and give extra points for the fastest implementation!

Details

Please name your structures Seq1, ..., Seq5, to make our lives easier at grading time.

Sequence Signature

signature SEQUENCE = sig
  type 'a sequence
  val create: unit -> 'a sequence
  val empty:  'a sequence -> bool
  val length: 'a sequence -> int
  val nth:    'a sequence -> int -> 'a 
  val insert: 'a sequence -> int -> 'a -> 'a sequence 
  val delete: 'a sequence -> int -> 'a sequence
  val concat: 'a sequence -> 'a sequence -> 'a sequence
  val split:  'a sequence -> int -> (('a sequence)*('a sequence))
  val map:    ('a -> 'b) -> 'a sequence -> 'b sequence
  val equal:  ''a sequence -> ''a sequence -> bool
end

Test Rig Signature

signature TESTER = sig
  exception exProblem of string
  val run: unit -> bool
end
Also define 
functor SeqTester(seq:SEQUENCE):TESTER = ...
that takes a structure with the SEQUENCE signature and generates a structure with the TESTER signature that exercises said implementation of sequences.

Handing in your solution

Your files should contain everything necessary for the assignment. Do not run the script several times to hand in different portions of the assignment, turn in all files at once, each time.

Please be sure your file loads and runs properly on sml as installed on the CS machines. Turn it in by running eg 

~bap/bin/handin hw6-vector.sml hw6-list.sml hw6-prefixlist.sml hw6-tree.sml hw6-skiplist.sml testseq.sml
on a regular UNM CS machine.

Due: 3:30pm, Nov 12: structures for lists and vectors.
Due: midnight, Nov 17: test jig, and other structures except last.
Due: 3:30pm, Nov 21: last sequence structure.

Barak Pearlmutter <bap@cs.unm.edu>
Shawn Stoffer <storm@cs.unm.edu>