10 Homework 6B
Due:
Thursday, 2/15 at 9PM
This assignment is SOLO, and entirely AUTOGRADED.
What to Download:
Please start with this file, filling in where appropriate, and submit your homework to the HW6B assignment on Gradescope. This page has additional information, and allows us to format things nicely.
10.1 Problem 1
Give a polymorphic signature (using All) to the following function tree-map, which is the list abstraction map abstracted to work over trees that have values (of arbitrary type) at their leaves.
| (define-struct leaf [value]) |
| (define-struct node [left right]) |
| (define-contract (Tree X) (OneOf (Leaf X) (Node (Tree X) (Tree X)))) |
| (define (tree-map f t) |
| (cond [(leaf? t) (make-leaf (f (leaf-value t)))] |
| [(node? t) (make-node (tree-map f (node-left t)) |
| (tree-map f (node-right t)))])) |
10.2 Problem 2
The identity function has signature (All (X) (-> X X)), a signature that actually ensures that the function has to behave as the identity. The reason is, since the function must return an X, the only thing it can do is return its argument, unchanged, as there are no other places it could find an X.
In this problem, we want you to write the four possible functions that have signature (All (X) (-> Boolean X X X)). i.e., the function takes a Boolean and two values of type X, and returns one of them. Like the signature of the identity function above ensures that there is only one function (there might be many ways of writing the function in code, but they will all behave the same), this signature ensures that there are only four possible functions. We want you to write them all as p2a, p2b, p2c, and p2d. It’s not important which is which, they just all have to behave differently.
NOTE: Do not use random in this assignment, including via contract-generate (or mutable state, if you’ve found that).
| (: p2a (All (X) (-> Boolean X X X))) |
| (define (p2a b x1 x2) ...) |
| (: p2b (All (X) (-> Boolean X X X))) |
| (define (p2b b x1 x2) ...) |
| (: p2c (All (X) (-> Boolean X X X))) |
| (define (p2c b x1 x2) ...) |
| (: p2d (All (X) (-> Boolean X X X))) |
| (define (p2d b x1 x2) ...) |
10.3 Problem 3
Existential types allow us to hide details that are not relevant, or alternately, to define interfaces that many different implementations may hide behind. In this problem, we want you to define a contract, using Exists and Tuple to define a type ShapeArea combined with a way of getting its area. This same type should be the return type of both rectangle-with-area and circle-with-area, showing that it forms an interface.
| (define-struct rectangle [width height]) |
| (define-contract Rectangle~ (Rectangle Real Real)) |
| (: rectangle-area (-> Rectangle~ Real)) |
| (define (rectangle-area r) |
| (* (rectangle-width r) (rectangle-height r))) |
| (define-struct circle [radius]) |
| (define-contract Circle~ (Circle Real)) |
| ; Good enough for NASA |
| ; https://www.wired.com/story/how-much-pi-do-you-really-need/ |
| (define PI 3.141592653589793) |
| (: circle-area (-> Circle~ Real)) |
| (define (circle-area c) |
| (* (sqr (circle-radius c)) PI)) |
| (define-contract ShapeArea ...) |
| (: rectangle-with-area (-> Rectangle~ ShapeArea)) |
| (define (rectangle-with-area r) (list r rectangle-area)) |
| (: circle-with-area (-> Circle~ ShapeArea)) |
| (define (circle-with-area c) (list c circle-area)) |