CS 2500 Honors Lab 7: Abstraction and Functions as Values

Abstraction Over Values

Sometimes when we solve problems, we find that the solution to one problem looks a lot like the solution to another one. Check out these functions and data definition: (from now on we will leave out the definition for lists, and use the [listof X] notation)

;; A [listof Number] is one of
;;  -- empty
;;  -- (cons Number [listof Number])

;; lon-add2 : [listof Number] -> [listof Number]
;; Add two (2) to each element of the given list of numbers
(define (lon-add2 lon)
  (cond [(empty? lon) empty]
        [else (cons (+ (first lon) 2)
                    (lon-add2 (rest lon)))]))

;; lon-add5 : [listof Number] -> [listof Number]
;; Add five (5) to each element of the given list of numbers
(define (lon-add5 lon)
  (cond [(empty? lon) empty]
        [else (cons (+ (first lon) 5)
                    (lon-add5 (rest lon)))]))

Is it clear what each function does? You are hopefully asking "Why would you do that?!" since they are almost exactly the same.

Exercise 1:

Write a function named lon-add-n that abstracts both of the functions above, taking an extra argument, which is the number to be added to each element.

Note: Follow the recipe for abstraction...

Exercise 2:

Rewrite (recreate) both lon-add2 and lon-add5 using your more general function, and write a few tests for each to be sure they work as expected.

Abstraction Over Functions

As you've seen in class, functions in DrRacket (as in many other nice programming languages) are considered data just like 5 or (list 'hello). We can name them with defines, return them from and pass them to other functions, and even store them in structures.

Suppose we implemented this function:
;; lon-sub-n : [listof Number] Number -> [listof Number]
;; Subtract 'n' from each element of the given list of numbers
(define (lon-sub-n lon n) ...)

This looks like the function you just implemented right? Substitute - for + and they are actually the same. Substitution... Isn't that just what "plugging-in" does?

Exercise 3:

If you were to abstract these two functions into a single, more general one, What would be its contract?

Be Precise... you will need another arrow (->) in it.

Exercise 4:

Write the function, name it lon-do-n, that abstracts both of the functions, taking an extra argument, which is the function to be applied to each element and the given number.

Exercise 5:

Rewrite (or write) both lon-add-n and lon-sub-n using your more general function, and write a few tests for each to be sure they work as expected.

More Abstraction

Important: Change your DrRacket language level to “Intermediate Student with lambda” (and there was much rejoicing...). If local isn't familiar then please review Section 18 of HtDP.

Here's a function that returns a function:

;; add-n : ??
(define (add-n n)
  (local [(define (f m) (+ n m))]

If you get confused by all the variable names, then run "Check Syntax" and use your mouse to see how all of them interact.

Exercise 6:

Fill in its contract and give it a meaningful purpose statement... again, you need another arrow, right?

Exercise 7:

Write some tests for it. After you figure out the purpose, this should be easy.

Hint: In order to test a function that returns a function, you will have to apply the result to something, e.g.:

     ((add-n 5) 7) ;; => 12

If it makes you more comfortable, use a definition to name the function that is returned, then call that on an argument.

Exercise 8:

Review DrRacket's built-in abstract functions here. Use map to rewrite lon-add-n and lon-sub-n using add-n from above (remember, subtraction is like adding a negative number, right?). Use your check-expects from earlier to be sure your newly designed functions operate the same as before. Question: Do all the contracts match up accordingly?

DrRacket's "loop" functions

Remember all that stuff we did with lists and structural recursion? Well, DrRacket has built-in functions to help us write functions that deal with lists. (See here.)

For the functions below, remember that DrRacket has the functions odd? and even? built-in; both are (Number -> Boolean).

Exercise 9:

Design a function all-odd? that takes a [listof Number] and returns true if all the numbers in the list are odd, and false otherwise. Hint: use andmap.

Exercise 10:

Design the same function, call it all-odd-2?, but use ormap this time. Hint: if all the numbers are odd, then none of them are even, right?

Exercise 11:

Design the function between that takes two numbers (say low and high) and returns a list of all numbers from low to high-1 (inclusive). Use build-list.

Hint: The first argument to build-list is the length of the list that you want to build. The second argument is a function that takes an argument i and returns the item that you want to be at position i in the list (starting from 0!).

Exercise 12:

Using your function between, design the function evens that takes two numbers, and returns a list of all the even numbers in that range. Use filter.

Exercise 13:

Using foldr or foldl, implement the function sum that computes the sum of all the elements in a list of numbers.

Study this function definition:

;; minus-all : Number [listof Number] -> Number
;; Subtract all the numbers in the list from the given one
(define (minus-all n lon)
  (foldl - n lon))

(minus-all 20 empty)            ;==> 20
(minus-all 20 (list 5 2))       ;==> 13
(minus-all 20 (list 5 4 3 2 1)) ;==> 5

Exercise 14:

Why doesn't this function work? Fix the function so that it produces the correct results. Hint: subtraction is not commutative... i.e., it is order dependent.

Finally Something Fun...

Ok... now that we're through all that, we'll design some animation functions, and put them all together with the loop functions to get a fun little program.

Here's our world definitions:

(require 2htdp/image)
(require 2htdp/universe)

;; ****************************
;; A World is a  [listof Rect]

;; A Rect is:
;;     (make-rect Posn Posn String)
;; where the first posn is the rect's current position, the second
;;   is its velocity (speed in x and y) and the string is its color
(define-struct rect (pnt vel color))

;; Gravitational Acceleration
(define G-ACCEL 2)

;; Width and Height of each rectangle
(define RW 10)
(define RH 10)

;; Width and Height of the Scene
(define SW 400)
(define SH 400)


In other words, our world is a list of Rect (blocks). Each one knows where it is (pnt), its velocity vector (vel) and its color.

Exercise 15:

Design the function gravity ([listof Rect] -> [listof Rect]) that adds (remember Y is upside down on the screen) the G-ACCEL constant to the y component of the velocity of each element of the World. Use map.

Exercise 16:

Design the function move ([listof Rect] -> [listof Rect]) that moves each Rect one step in the direction it is headed. Use map.

Hint: (Xnew, Ynew) = (Xold + Xvel, Yold + Yvel)

Exercise 17:

Design the function only-on-screen ([listof Rect] -> [listof Rect]) that removes the Rects that are not on the screen from the world. Use filter.

Exercise 18:

Design the function draw ([listof Rect] -> Scene) that draws all the Rects into an empty-scene, size (SW by SH). Use foldl. Hint: Fill in the general contract of foldl with specific "types" (Rect and Scene), then design a local function to match.

Finally: Now, as a final step, use this code to finish off the World simulation. Drag your mouse on the screen to see what happens!!
;; new-rect : Number Number -> Rect
;; Create a new Rect at the given point
(define (new-rect x y)
  (make-rect (make-posn x y)
             (make-posn (- (random 14) 7) (- (random 10)))
             (cond [(= (random 2) 0) "red"]
                   [else "orange"])))

;; tick : World -> World
;; Make updates to the world... gravity, movement, and filter
(define (tick lob)
  (only-on-screen (move (gravity lob))))

;; mouse : World Number Number String -> World
;; On drag, create random Rects
(define (mouse lob x y me)
  (cond [(string=? me "drag") (cons (new-rect x y) lob)]
        [else lob]))

(big-bang empty
          (on-tick tick)
          (on-mouse mouse)
          (on-draw draw))

If you finish early, try having the rectangles bounce when they reach the bottom, or when they collide with each other!