Homework 8

Please read chapter 15: Designing Abstractions and chapter 16: Using Abstractions in the textbook.

Be sure to include type, purpose, definition and tests for all functions.

Include the following at the top of your homework:

#lang typed/racket

(require "../include/uchicago151.rkt")
(require typed/2htdp/image)
(require typed/test-engine/racket-tests)

And include (test) at the bottom of your homework.

Problem 1

You should reuse the same design from lab 3. You will be writing a function that works as follows:

(: main (-> Image Image))

(main (design 64)) should produce this, which is exactly 64*4=256 pixels across:

(main (design 128)) should produce this, which is exactly 128*4=512 pixels across:

By looking closely at this image, you can deduce the recursive construction involved. The pattern is full of self-similarities and mirrorings. Exploit them by writing auxiliary functions to assist in its construction.

Note that the output of main must produce an image that is exactly four times as wide and four times as tall as its input. Make sure to satisfy that condition in all cases, or things are likely to go haywire.

Problem 2

We have worked with a quadratic equation by passing around three Real parameters. We improved on this by placing these coefficients together into a struct. With this improvement, we can pass around Quadratics with the coefficients bundled together into one object, and we can return Quadratics. (We can't return three Reals because functions have a single return value.)

Now that we have lists to work with, we can generalize beyond quadratics to full-fledged polynomials, including arbitrarily high powers of x. With this new representation, we can compute with polynomials like, for example, 5x⁷ + 3x⁵ + 2x + 1.

We will allow Real coefficients but only Nonnegative-Integer exponents. While we will use an Integer to store the exponent, we will never work with negative exponents.

Here are the specific data type definitions we will be working with:

(define-struct Term
  ([coeff : Real]
   [exp   : Nonnegative-Integer]))

(define-type Polynomial (Listof Term))

Write the following functions:

• (: term->string (-> Term String))

  which will create a string representing a term. For example (term->string (Term 3 2)) should be the string "3x^2" and (term->string (Term 4 1)) should be the string "4x". You will need special cases for handling terms with exponent equal to zero or one and terms with coefficient equal to zero or one.

• (: polynomial->string (-> Polynomial String))

  which will create a string representing a polynomail. For example, (polynomial->string (list (Term 3 7) (Term 4 2) (Term 5 0))) should be the string "3x^7 + 4x^2 + 5".

• (: sorted-desc? (-> Polynomial Boolean))

  to check that powers in the polynomial appear in strictly descending order. This will be true if the first exponent is larger than the second, and the second is larger than the third, and so on. Note this does not involve the coefficients.

• (: value-at (-> Polynomial Real Real))

  will compute the value of the polynomial at some given x position. For example, (value-at (list (Term 3 2) (Term 4 0)) 2) should give the result 16.

• (: poly->func (-> Polynomial (Real -> Real)))

  to create a function that will compute the polynomial. For example, calling (poly->func (list (Term 3 2) (Term 5 0))) should produce a function on real numbers that will compute 3x²+5

• (: even-terms (-> Polynomial Polynomial))

  to create a new polynomial that has only the terms with even exponents of the input polynomial

• (: poly-add (-> Polynomial Polynomial Polynomial))

  to add two polynomials. For example, (poly-add (list (Term 3 7) (Term 4 2) (Term 5 0)) (list (Term 2 5) (Term 1 2))) should be (list (Term 3 7) (Term 2 5) (Term 5 2) (Term 5 0)). If either input is not ordered by exponents descending, raise an error.

• (: sum-polys (-> (Listof Polynomial) Polynomial))

  to add multiple polynomials. If any input is not ordered by exponents descending, raise an error.

Problem 3

Use the following polymorphic pair type:

(define-struct (Pair A B)
  ([a : A]
   [b : B]))

Define two functions zip and unzip. The zip function should take a pair of lists as input and output a list of pairs. For example (zip (Pair (list 1 2 3) (list 4 5 6))) should evaluate to (list (Pair 1 4) (Pair 2 5) (Pair 3 6)) and (zip (Pair (list 1 2 3) (list "a" "b" "c"))) should evaluate to (list (Pair 1 "a") (Pair 2 "b") (Pair 3 "c")). If the lists in the input pair have unequal length, it is an error.

The unzip function should be the inverse of zip. Be sure to use the correct polymorphic type for your functions. You should not use the type Any.

Submit your work in your repository in hw8/hw8.rkt by noon Friday, July 7.