Problem Set 8h

This is the honors version of Problem Set 8.


home work!

Programming Language ISL+

Purpose This problem set concerns the use of existing abstractions, as well as local and lambda.

Finger Exercises HtDP/2e: 221, 222, 223, 225


Problem 1 : Tetris Revisited

Edit your Tetris project. Be sure to fix any and all problems that your graders have discovered.

Next, you are to use local and "loops" (i.e., abstractions such as map, foldr, filter, etc.) wherever your functions may benefit from them, especially for the lists of objects in your project. You may also use lambda terms in place of locally-named helper functions if you wish.

You should notice that the length of your program decreases considerably.

Finally, give your program the missing feature that will make it a full Tetris game: whenever some row of the board is completely full of blocks, it should be deleted, and everything above shifted down one row.

Note: you should remove templates from your code before you hand it in. (Templates are handy for developing code, but do not need to appear in the final program.)


The following problems deal with Sequences, a ubiquitous type of data in both computer science and mathematics. There are many types of sequences all of which can be represented with various data structures. So, of course, we will abstract over them.

Problem 2 : Finite Increasing Arithmetic Sequences

; A FIAS (Finite Increasing Arithmetic Sequence) is a:
; (make-fias Number Number Positive)
; where (make-fias min max step) includes all numbers (possibly none)
; of the form min+k*step, where k is a natural number,
; such that min+k*step < max.
(define-struct fias (min max step))
(define FIAS-1 (make-fias 0 1 0.25))
FIAS-1 represents the sequence [0, .25, .5, .75]. Note that 1 is not included.

  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:
; - String
; - Natural
; - FIAS
; - [Listof X]
; interpretation: A Sequence is a (possibly empty) ordered sequence
; of elements, where:
; - a String's sequence is its individual characters (substrings of length 1)
; and is a [Sequence String]
; - a String s's sequence is its individual characters (substrings of length 1)
; and is a [Sequence 1String] (where 1String is a String of length 1)
; - 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, "" and 0 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. Use sequence-foldr and λ.

  6. ; 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.  

    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 λ.


Problem 5 : Extra Credit

Design a function distinct, which consumes a [Sequence [Sequence X]] and a [Equality X] and determines if all sequences are totally distinct, i.e. if any element x appears in more than one sequence, it will return false. A sequence of sequences are totally distinct 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.