2 Assignment 2: Representation Independence

Guidelines for this assignment

• Place all of your code in a file named a2.rkt, and submit it via the autograder. Please make sure your file has exactly this filename, and that it runs, before submitting.

• You may find memv and filter useful.

Rectangles

An upright rectangle is a rectangle in the XY plane whose edges are parallel to the X and Y axes. For a type T to represent upright rectangles, we require these methods:

• from-center : Number Number Number Number -> T is a procedure that constructs an upright rectangle by taking its center X coordinate, its center Y coordinate, its width, and its height.

• from-corners : Number Number Number Number -> T is a procedure that constructs an upright rectangle by taking the X and Y coordinates of one corner and the X and Y coordinates of the opposite corner.

• area : T -> Number is a procedure that takes an upright rectangle and returns its area.

• contains? : T Number Number -> Boolean is a procedure that takes an upright rectangle and the X and Y coordinates of a point and returns a boolean to indicate whether the point is inside the rectangle.

• scale : Number T -> T is a procedure that takes a positive number and an upright rectangle and returns a new upright rectangle with the same center but whose width and height are multiplied by the given number.

These methods are the five elements of a list. For instance, when given any correct representation of upright rectangles, the following procedure

(define smoke-test-rect

(lambda (rect)

(match rect

[(list from-center from-corners area contains? scale)

(let ([r (scale 2 (from-corners 6 4 3 5))])

(cons (area r)

(map (lambda (y)

(map (lambda (x) (contains? r x y))

'(0 1 2 3 4 5 6 7 8 9)))

'(9 8 7 6 5 4 3 2 1 0))))])))

returns

(12

(#f #f #f #f #f #f #f #f #f #f)

(#f #f #f #f #f #f #f #f #f #f)

(#f #f #f #f #f #f #f #f #f #f)

(#f #f #f #f #f #f #f #f #f #f)

(#f #f #t #t #t #t #t #t #f #f)

(#f #f #t #t #t #t #t #t #f #f)

(#f #f #f #f #f #f #f #f #f #f)

(#f #f #f #f #f #f #f #f #f #f)

(#f #f #f #f #f #f #f #f #f #f)

(#f #f #f #f #f #f #f #f #f #f))

1. The word “inside” above can mean to include or to exclude the edges of the rectangle. Define a procedure includes-edge? that takes a representation of upright rectangles and returns a boolean to guess whether it includes the edges. Invoke the contains? method just once.

2. Define center-rect to be a representation of upright rectangles that stores each rectangle as a list of four numbers: its center X coordinate, its center Y coordinate, its width, and its height.

   Follow the grammar below to decide if your code needs to be recursive:

   T

   =

   (Number Number Number Number)

   Finish the five definitions in the following skeleton.

   (define center-rect-from-center ...)

   (define center-rect-from-corners ...)

   (define center-rect-area ...)

   (define center-rect-contains? ...)

   (define center-rect-scale ...)

   (define center-rect

   (list

   center-rect-from-center

   center-rect-from-corners

   center-rect-area

   center-rect-contains?

   center-rect-scale))

3. Define corners-rect to be a representation of upright rectangles that stores each rectangle as a list of four numbers: its minimal X coordinate, its minimal Y coordinate, its maximal X coordinate, and its maximal Y coordinate.

   Follow the grammar below to decide if your code needs to be recursive:

   T

   =

   (Number Number Number Number)

   Finish the five definitions in the following skeleton.

   (define corners-rect-from-center ...)

   (define corners-rect-from-corners ...)

   (define corners-rect-area ...)

   (define corners-rect-contains? ...)

   (define corners-rect-scale ...)

   (define corners-rect

   (list

   corners-rect-from-center

   corners-rect-from-corners

   corners-rect-area

   corners-rect-contains?

   corners-rect-scale))

Sets

For a type T to represent finite sets of natural numbers, we require these methods:

• empty : -> T take no argument an returns the empty set.

• single : NaturalNumber -> T is a procedure that takes a natural number and returns the set that just contains that number.

• union : T T -> T is a procedure that takes two sets and returns their union. In other words, the result is the set that contains the numbers that are in one or both of the input sets.

• intersection : T T -> T is a procedure that takes two sets and returns their intersection. In other words, the result is the set that contains the numbers that are in both of the input sets.

• difference : T T -> T is a procedure that takes two sets and returns their difference. In other words, the result is the set that contains the numbers that are in the first input set but not the second.

• contains? : T NaturalNumber -> Boolean is a procedure that takes a set and a natural number and returns a boolean to indicate whether the given set contains the given number.

These methods are the six elements of a list. For instance, the following procedure returns '(3) when given any correct representation of finite sets of natural numbers:

(define smoke-test-natset

(lambda (natset)

(match natset

[(list empty single union intersection difference contains?)

(let ([s (difference (union (single 3) (single 5))

(union (single 5) (empty)))])

(filter (lambda (x) (contains? s x))

'(0 1 2 3 4 5 6 7 8 9)))])))

4. One representation of finite sets of natural numbers is to put numbers in a list. We don’t even need to remove duplicates:

   (define sparse-natset-empty

   (lambda ()

   '()))

   (define sparse-natset-intersection

   (lambda (s1 s2)

   (filter (lambda (x) (memv x s2)) s1)))

   (define sparse-natset-difference

   (lambda (s1 s2)

   (filter (lambda (x) (not (memv x s2))) s1)))

   (define sparse-natset-contains?

   (lambda (s x)

   (memv x s)))

   (define sparse-natset

   (list

   sparse-natset-empty

   list

   append

   sparse-natset-intersection

   sparse-natset-difference

   sparse-natset-contains?))

   Define a new procedure sparse-natset-union and replace the method append with sparse-natset-union in sparse-natset so that duplicates are removed. (Why don’t you need to change the intersection and difference methods?)

5. Define dense-natset to be another representation of finite sets of natural numbers, where T is lists of booleans. For instance, a set containing only number 5 can be represented as '(#f #f #f #f #f #t), meaning that only 5 shows up in the set. Similarly, (single 3) should be '(#f #f #f #t), and (union (single 3) (single 5)) should be (list #f #f #f #t #f #t).

   Follow the grammar below to decide if your definitions needs to be recursive:

   Boolean		=		#f
   		|		#t
   T		=		()
   		|		(Boolean . T)

   Finish the six definitions in the following skeleton.

   (define dense-natset-empty ...)

   (define dense-natset-single ...)

   (define dense-natset-union ...)

   (define dense-natset-intersection ...)

   (define dense-natset-difference ...)

   (define dense-natset-contains? ...)

   (define dense-natset

   (list

   dense-natset-empty

   dense-natset-single

   dense-natset-union

   dense-natset-intersection

   dense-natset-difference

   dense-natset-contains?))

6. Define function-natset to be yet another representation of finite sets of natural numbers, where T is functions from natural numbers to booleans.

   For instance, (union (single 3) (single 5)) should be a function that takes a natural number as input, and returns #t if the input is 3 or 5, or #f otherwise.

   Finish the six definitions in the following skeleton.

   (define function-natset-empty ...)

   (define function-natset-single ...)

   (define function-natset-union ...)

   (define function-natset-intersection ...)

   (define function-natset-difference ...)

   (define function-natset-contains? ...)

   (define function-natset

   (list

   function-natset-empty

   function-natset-single

   function-natset-union

   function-natset-intersection

   function-natset-difference

   function-natset-contains?))

Just Dessert

7. The lambdas with only one argument can be used to define a representation of natural numbers, called Church numerals, and arithmetic over them. For instance, c5 is the definition of the Church numeral for 5.

   > (define c0 (lambda (f) (lambda (x) x)))

   > (define c5 (lambda (f) (lambda (x) (f (f (f (f (f x))))))))

   > ((c5 add1) 0)

   5

   > ((c0 add1) 0)

   0

   The following is a definition for Church plus, which performs addition over Church numerals.

   > (define c+ (lambda (m)

   (lambda (n)

   (lambda (add1)

   (lambda (zero)

   ((m add1) ((n add1) zero)))))))

   > (let ((c10 ((c+ c5) c5)))

   ((c10 add1) 0))

   10

   One way to understand the definition of c+ is that, when provided two Church numerals, it returns a function that, when provided a meaning for add1 and a meaning for zero, it returns the meaning of the sum of m and n.

   Your task, however, is to implement csub1, Church predecessor. The following tests should pass.

   > (((csub1 c5) add1) 0)

   4

   > (((csub1 c0) add1) 0)

   0

   In the second case, the Church predecessor of Church zero is zero, as we haven’t a notion of negative numbers.

   This was a difficult problem, but it’s fun, so don’t Google it. If you think it might help though, consider taking a trip to the dentist.