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:
We will not only grade them, we will also benchmark them and give extra points for the fastest implementation!
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
signature TESTER = sig exception exProblem of string val run: unit -> bool endAlso 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.
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.smlon 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.