Optional: Homework # 14
due Tuesday, March 30, 4:00 PM

This is an optional homework is provided by request. You are under no obligation to do it. Getting a grade on this homework cannot reduce your final grade (although it may temporarily reduce your current weighted average until the last Homework is completed).

Warning: the grade is not added to your final score, but rather will take the place of a lower Homework score (if any). Thus it is not worthwhile to do this Homework until you have completed Homework #7. It is much more beneficial to get 100% on Homework #7 than to get 50% on each of this Homework and Homework #7.

Appendable Sequences

An efficient appendable sequence can be described similarly to a problem on the midterm, but with an extra count in Append nodes that gives the sum of elements in both sequences.

datatype 'a sequence = None 
                     | Single of 'a
                     | Append of (int * 'a sequence * 'a sequence);

Write the following functions that use this datatype:

1. A sequence is valid if it includes no proper None subsequences (but of course None is itself valid). A valid sequence must also have the correct number of elements stored in each Append node inside the sequence. Write a function isValid that is true if and only if the sequence is valid.

   The rest of the functions may assume any input parameter sequence is valid.

2. Write a constant-time function that returns the size of a sequence. It should be called size.
3. Write an append function that takes two sequences and appends them. The result should be valid assuming both parameter sequences were valid.
4. Write a function nth that returns the nth element of a sequence using 0-based indexing. It should be $O(\log n)$ if the sequence is balanced (although there is no requirement that the sequence be balanced). The size function will be useful.
5. Write a function position that returns an ``int option'' that gives the position of that element in a sequence. If it is not in the sequence, position should return NONE (not to be confused with None, the empty sequence). The option data type is predefined:

   
   datatype 'a option = SOME of 'a | NONE;
   

6. Write a function foldright that does the equivalent of foldr, but does it on a sequence instead of a list.

The functions should have the following ML types:

val isValid = fn : 'a sequence -> bool
val size = fn : 'a sequence -> int
val append = fn : 'a sequence * 'a sequence -> 'a sequence
val nth = fn : int -> 'a sequence -> 'a
val position = fn : ''a -> ''a sequence -> int option
val foldright = fn : ('a * 'b -> 'b) -> 'b -> 'a sequence -> 'b

All these functions should be declared with the data type in the file sequence.sml in a directory named homework14 in your AFS class volume.

Submitting Your Work

You submit your program work by putting it in the homework14 directory in your AFS class volume. You will need to create this directory. You may do all your work in this directory, or you may wish to do your work in a different directory and copy things when correct into this directory. In any case, you will lose permission to write things in this directory after the deadline, which is 4:00pm on Tuesday, March 30th. In other words, you must be done before lecture starts.

The homework14 directory should include the following:

• sequence.sml

If you want this Homework to be graded, you must send email to the instructor at boyland@cs.uwm.edu.

About this document