Problem Set 6

Purpose This problem set concerns complex uses of natural number recursion, higher order functions, and abstraction.

This assignment is due on Monday, November 2 at 11:59pm. Next week’s assignment will get us back to normal Thursday schedule.

For this problem, you are going to draw a standard English ruler (ignore marking it with numbers), with tick marks for inches, half-inches, quarter-inches... Your rulers are superior to typical store-bought ones: the tick marks will go down to an arbitrary precision, or depth.

Let’s say the height of an inch’s mark is 1, the height of a half inch is 1/2, the height of a quarter inch is 1/4. Surely, there is a pattern here. At depth n (1 for an inch, 2 for a half inch, etc.), the height of the tick is (expt 1/2 (sub1 n)). With this as our starting point, let’s go step-by-step through the process of making and then drawing this ruler.

1. Design a function interleave that takes two [List-of X] and produces a list of their items, alternating from each list. If the lists have different lengths, that’s ok; just finish with all the remaining items of the longer list. Although it may seem like this function would require a helper or local function, you actually do not need one.

2. Define the constant ruler-ticks-2x1 that represents the heights of the tick marks of a 2 inch ruler that only uses full inch marks.

3. Define the constant ruler-ticks-2x1/2 that represents the heights of the tick marks of a 2 inch ruler that uses full inch marks and half inch marks.

4. Define the constant ruler-ticks-2x1/4 that represents the heights of the tick marks of a 2 inch ruler that uses full inch marks, half inch marks, and quarter inch marks.

5. Examine the relationship between ruler-ticks-2x1 and ruler-ticks-2x1/2, then compare that to the relationship between ruler-ticks-2x1/2 and ruler-ticks-2x1/4. What are the similarities between the two pairs? Record your observations in a comment, and refer to previously defined functions if appropriate.

6. Design the function ticks-for-depth that takes a natural number depth and outputs a [List Number] that represents the heights of tick marks on a ruler of one inch that goes to depth depth.

7. Design the function make-ticks that takes two natural numbers inches and depth that produces a [List-of Number] that represents the heights of tick marks on a ruler of inches inches that goes to depth depth. Note that following the template for natural numbers may result in computing the same piece of information many times. Be sure to structure your code so this is not the case.

8. Design a function draw-tick that given a single tick height height and depth depth, draws a black line of height (* PIXELS-IN-INCH height) in the bottom right corner of a 'beige rectangle of height PIXELS-IN-INCH and width (* (expt 1/2 (sub1 depth)) PIXELS-IN-INCH). (You may want to use add-line for this.)

9. Design ruler, which takes two positive numbers, one representing inches and the other depth, that produces the desired result. For example, (ruler 6 5) should produce:

   

   This function must be defined with foldr. The constant empty-image will be helpful. This function must not use map.

Problem 2 : Finite Increasing Arithmetic Sequences

1. Design a function increment that consumes a FIAS and changes its min value to be the sum of the step and original min. Note that increment is to a FIAS as rest is to a [Listof X], because it returns a FIAS that represents the rest of the sequence it used to.

2. Design a function empty-fias?, which will return true if a FIAS contains no values.

3. Design a function fias->list, that creates a [Listof Number] of all the numbers in a FIAS (in order).

4. Design a function sum-fias, that sums all of the elements of a FIAS.

Problem 3 : Sequences

; A [Sequence X] is one of:

; - Natural

; - FIAS

; - [Listof X]

; interpretation: A Sequence is a (possibly empty) ordered sequence

; of elements, where:

; - a Natural number n's sequence is [n-1, n-2... 2, 1, 0] (n is not included)

; and is a [Sequence Natural]

; - a FIAS's sequence is the numbers it represents

; and is a [Sequence Number]

; - a [Listof X]'s sequence is its elements

; and is a [Sequence X]

Sequences can come in many shapes and sizes. Be sure that you test on many different types of sequences, not just lists.

1. Design the template for a [Sequence X].

2. Design a function sequence-empty?, that determines if a sequence is empty. A sequence is empty if it contains no values. For example, 0 and empty are both empty sequences.

3. Design a function sequence-first, that outputs the first element of a non-empty sequence.

4. Design a function sequence-rest, that outputs a sequence identical to a non-empty sequence, except it is missing the first value.

5. We now know a [Sequence X] has a very similar recursive structure to a [Listof X], and thus all of the elements to all sequences can be accessed via sequence-empty?, sequence-first, sequence-rest.

   Re-write the template for sequences using sequence-empty?, sequence-first, and sequence-rest.

From now on, use this template instead of the one you wrote before.

Problem 4 : Sequences - Now With Abstraction

1. Design a function sequence-foldr, which will recursively apply a function f to the elements of the sequence s onto a base case b, where the first function call will be on the first element of the sequence. The header is written for you:

   ; sequence-foldr : [X Y -> Y] Y [Sequence X] -> Y

   ; fold the elements of s onto b with f

   (define (sequence-foldr f b s)

   ...)

2. Rewrite sum-fias using sequence-foldr.

3. Design the function sequence-map, which will return a sequence with a function f applied to all of a sequence’s elements. Write it with sequence-foldr and λ. The header is written for you:

   ; sequence-map : [X -> Y] [Sequence X] -> [Sequence Y]

   ; applies f to all of the elements of s

   (define (sequence-map f s)

   ...)

4. So, we can properly write sequence-foldr, sum-fias with sequence-foldr, and sequence-map with sequence-foldr. However, it would be wrong to rewrite fias->list with sequence-map.

   sequence-map outputs a [Sequence Y]. fias->list specifically calls for a [List Number]. Although sequence-map is written with lists, this does not have to be the case. Someone else could add a new type of data structure to the data definition of [Sequence X], rewrite sequence-map with it, and they wouldn’t be wrong. fias->list, if written with sequence-map, would no longer output a [List Number], but would instead output who knows what.

   Relying on specification - in this case, the signature of the function - instead of the implementation - in this case, the specific data structure the function returns - is essential for proper program design. The implementation can change at any time, as long as it follows the specification.

   Relying on implementation is almost guaranteed to result in broken code.

   Rewrite fias->list with sequence-foldr.

5. Design a function sequence-ormap, which determines if at least one element in a sequence passes a test, where the test is an input to sequence-ormap.

6. In a comment, specify why it would be non-ideal to write sequence-ormap with sequence-foldr.

Problem 5 : Sequences - Now With Equality

; An [Equality X] is a [X X -> Boolean] that returns true if

; and only if the two arguments passed to it are exactly the same.

; E.g., =, string=?, and symbol=? are all examples

; of equalities.

1. Design a function sequence-member, which consumes an X, a [Sequence X], and an [Equality X], and determines if that element is in the sequence. Use sequence-ormap and λ.

2. Design a function pairwise-disjoint, which consumes a [Sequence [Sequence X]] and a [Equality X] and determines if all sequences are totally pairwise disjoint, i.e. if no element appears in more than one sequence. A sequence of sequences is pairwise disjoint if it is empty or if none of the elements of the first sequence appear in any of the rest of the sequences and the rest of the sequences are also distinct.

   Note the two bolded words: they imply a "nested" loop, in that every element of one sequence must be checked against every other sequence. Previously, we would have had to write a helper for this function, but now with looping functions, we do not need to.

   While not necessary, you may find it helpful to define sequence-andmap. Feel free to do so.

3. Design a function sequence=?, that consumes two [Sequence X] and an [Equality X] and determines if they are equal.

4. Design a function sequence-number=?, that consumes two [Sequence Number] and determines if they are equal. Note that sequence-number=? is an [Equality [Sequence Number]]. Both 3 and '(2 1 0) are examples of [Sequence Number] and they happen to be equal.

5. Design a function sequence-sequence=?, which given an [Equality X] will output an [Equality [Sequence [Sequence X]]].

These functions will be helpful for writing tests.

Problem 6 : Growing, Shrinking, and Combining Sequences

1. Design a function sequence-length that outputs the length of a sequence. Use sequence-foldr.

2. We have sequence-empty?, sequence-first, and sequence-rest. What are we missing? sequence-cons, of course!

   Design a function sequence-cons which puts an element at the start of a sequence. Note that you have no idea what data structure the sequence is given in, and that your function should act independently of that. Hint: can sequence-foldr help?

3. Design a function make-sequence-filter which, given a [X -> Boolean] p, will output a function that will filter a [Sequence X] by p.

4. Design a function sequence-append that will append two sequences together.

5. Design a function sequence-append-all that will flatten a sequence of sequences into one sequence.

Problem 7 : Extra Credit - Sequence Cartesian Product

We want you to design sequence-cartesian-product, which takes a [Sequence [Sequence X]] and returns a [Sequence [Sequence X]]. Let’s make clear what it has to do.

((sequence-sequence=? =) (sequence-cartesian-product '((0 1 2)  (3 4)))

'((0 3) (0 4) (1 3) (1 4) (2 3) (2 4)))

The above code should return true. Given the sequence '(0 1 2) and '(3 4), it outputs a [Sequence [Sequence Number]], each element of which contains two elements, where the first element came from the first sequence and the second came from the second seqeunce. It was also in an order such that everything beginning with 0 came first, and everything ending with 3 came before all that ended with 4, provided the first element was equal. Now, for a more formal specification...

The cartesian product of Sequences S-1, S-2... S-n is defined as a sequence of sequences of size n, where the kth element of a, a sequence in the output sequence, is from S-k. It is ordered in such a way that, if S-1 is the sequence x-1, x-2, x-3...x-y, all sequences beginning with x-1 appear before x-2, appear before x-3, etc. Then, within all sequences that begin with x-1, the ordering is defined the same way, except with S-2 taking the part of S-1, and so on.

Here’s another example to illustrate:

((sequence-sequence=? symbol=?)

(sequence-cartesian-product '((a b) (red green blue) (hutt putt)))

`((a red hutt)

(a red putt)

(a green hutt)

(a green putt)

(a blue hutt)

(a blue putt)

(b red hutt)

(b red putt)

(b green hutt)

(b green putt)

(b blue hutt)

(b blue putt)))

1. When tackling such problems, it’s always a good idea to have many ways to test our functions. We already have sequence-sequence=?, but let’s have another one for good measure. Design a function sequence-cartesian-product-length, that given a sequence of sequences will predict the length of sequence-cartesian-product applied to that sequence of sequences. This should be written with sequence-foldr.

2. Design sequence-cartesian-product. Warning: use of helpers will prevent you from getting lost! Here are some hints:

   • Use the magic of recursion and sequence-foldr to create the cartesian product of all sequences except the first one.

   • Write a helper that will sequence-cons one element onto every sequence in a sequence of sequences.

   • Do that to all of the elements in the first sequence and sequence-append-all of them together.