# 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:

- vector
- list
- prefix list
- binary tree
- 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>