Homework VII

1. [35 points]

Provide an algebraic specification (initial algebra semantics) of a sequence ADT. This is to describe sequences as we commonly understand them (e.g. Z).

The sort of the values to appear in sequences is written as 'Item' here -- for specificity you are welcome to use Int (or num in Miranda) in its place instead of a polymorphic type Here are the visible operations for sequences and their signatures (Seq is the TOI, others are pre-defined):

emp: -> Seq

add: Item x Seq -> Seq

cat: Seq x Seq -> Seq

get: Seq x Nat -> Item

len: Seq -> Nat

The informal description of these operations is as follows:

emp -- this is the initial, empty sequence

add(x, s) -- add value x at the end of sequence s

cat(s1, s2) -- return the sequence obtained by concatenating s1 and s2

get(s, n) -- return the nth item of sequence s

len(s) -- return the number of items in sequence s

In ADTs you are always allowed (unless otherwise stated) to introduce hidden functions of your choosing. However, when hidden functions are added you should discuss them informally as well as providing the equations that formally describe their behavior, and include tests to show that the two views are consistent.

Your specification should be prototyped and tested with Miranda. You should provide a script of tests that exhibit the correct behavior of each case of each operation. In addition to a paper submission listing your program and tests, please submit your Miranda source code (only) electronically using the 'submit' command to directory Hwk7 for class c181.

2. [35 points]

For this problem, you will expand the Miranda animation of the initial algebra version of Diller’s phone system in our class directory phonedbADT2.m (not phonedbADT.m which is the final algebra version). Informally, the intention is to add the operation 'SharedPhones' that takes a set of Persons as an argument, and returns the set of all phones which are shared by every Person in that set. For instance, if Person A is assigned phones {p1, p2, p3}, Person B is assigned phones {p2, p3, p4}, and Person C is assigned phones {p2, p3, p5}, then SharedPhones {A, B, C} should yield {p2, p3}.

Provide a suitable algebraic description for this operation. It's assumed that you will retain the use of Miranda's (sorted) lists as a pre-defined type to replace sets in the animation. Use the animation facilities to fully justify the correctness of your solution. In addition to submitting a printed script showing your tests, you should submit your Miranda code (only) electronically to our class (c181) submit directory Hwk7.

Hint: list comprehension can be especially helpful, as well as the utility function (as a hidden function) to determine a list of all the common items in a list of lists that has been placed in our class directory.