CS 2500 Lab 8: 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.

;; 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 should be asking, “Why would you do that?” since they are almost exactly the same.

Exercise 1:

Write several tests for each function, lon-add2 and lon-add5.

Exercise 2:

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

Be sure to write some tests. (You should have done that even if we didn't tell you.)

Exercise 3:

Rewrite (recreate) both lon-add2 and lon-add5 using your more general function. Make sure your new functions pass the tests you wrote for Exercise 1.

Abstraction Over Functions

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

Suppose I 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. Where is the only difference? This is a good candidate for abstraction.

Exercise 4:

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

Be precise. You will need another arrow (->) in it.

Exercise 5:

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 6:

Rewrite (or write) both lon-add-n and lon-sub-n using your more general function, and make sure each passes some reasonable tests.

More Abstraction

Important: Change your DrScheme 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, you can use Check Syntax and point to the variables to see how they all connect.

How do we use this function? Try it in the interactions window.

Exercise 7:

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

Exercise 8:

Write some tests for it. After you figure out the purpose, this should be easy. If it makes you feel better, then use definitions to name the function that is returned, then call that on an argument.

Exercise 9:

Review DrScheme's built-in list abstraction functions. Use map to rewrite lon-add-n and lon-sub-n using add-n from above. Use your tests from earlier to be sure your newly designed functions operate the same as before.

DrScheme's “loop” functions

We've written the same template for recursion on lists too many times. We don't need to all the time, because DrScheme has built-in functions (same link again) to help us write functions that deal with lists.

(Recall that DrScheme has the functions odd? and even? built-in, both with contract Number -> Boolean)

Exercise 10:

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 local and andmap.

Exercise 11:

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 is even.

Exercise 12:

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

Exercise 13:

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

Exercise 14:

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

Consider 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))

(check-expect (minus-all 20 '())           20)
(check-expect (minus-all 20 '(5 2))        13)
(check-expect (minus-all 20 '(5 4 3 2 1))  5)

Exercise 15:

Why doesn't this function work? Fix the function so that it matches its purpose and passes the tests. Hint: Subtraction is not commutative.

An Animation

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:

;; ****************************
;; 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/direction) 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 16:

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 17:

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 18:

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 19:

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

Use this code to finish off the World simulation. Drag your mouse on the scene to create random rectangles.
;; new-rect : Number Number -> Rect
;; Create a new (un-moving) 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 MouseEvent -> World
;; On drag, create random Rects
(define (mouse lob x y me)
  (cond [(mouse=? me "drag") (cons (new-rect x y) lob)]
        [else lob]))

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