Lab 11 Lambda
Purpose: The purpose of this lab is to provide you with some more practice with higher-order functions, and to demonstrate how they can lead very quickly to very fun code.
Textbook References: Chapter 17: Nameless Functions
We Are Many. We Are Lambda.
Goals: Practice using functions as data. Practice designing functions that produce functions. Practice using lambda to create anonymous functions. Practice with world programs.
We will design a game in which you can create many balls which move across the screen in various ways. The player can add new balls by clicking on the screen.
Much of the work here is with higher-order functions. When it comes to higher-order operations, signatures are there to keep you sane and give you a hint as to what’s going on. Heed their wisdom, as to go forward you must go back, and to touch the light you must pass beneath the shadow.
Sample Problem Provide a data definition for a Ball. A Ball should have a radius, a mode (solid or outline), a color, and a function that takes a Natural Number and produces a Posn indicating where the ball is at that time.
; A Ball is a (make-ball Nat Mode Color [Nat -> Posn]) (define-struct ball (r mode color placement)) ; - where r is the ball's radius ; - mode is the ball's mode ; - color is the ball's color ; - and placement is a function that, given the current time, ; outputs a new coordinate for the ball to be drawn at ; A Mode is one of: ; - 'solid ; - 'outline
Sample Problem Provide some examples of Balls.
(define HEIGHT 500) (define WIDTH 500) (define BALL-1 (make-ball 5 'solid 'red (λ (t) (make-posn 20 (modulo t HEIGHT))))) (define BALL-2 (make-ball 7 'outline 'blue (λ (t) (make-posn (modulo t WIDTH) 100))))
Sample Problem Write a template for functions that process a Ball.
; ball-temp : Ball -> ??? (define (ball-temp b) (... (ball-r b) ... (mode-temp (ball-mode b)) ... (ball-color b) ... (ball-placement b) ...)) ; mode-temp : Mode -> ??? (define (mode-temp m) (... (cond [(symbol=? m 'solid) ...] [(symbol=? m 'outline) ...]) ...))
Sample Problem Provide a data definition for a World. A World needs to keep track of the time (so it knows where the balls should go) and all of its Balls.
; A World is a (make-world Nat [List-of Ball]) (define-struct world (t balls)) ; - where t is the amount of time that has passed ; - and balls is the balls of the world
Sample Problem Provide some examples of Worlds.
Sample Problem Write a template for functions that process a World.
; world-temp : World -> ??? (define (world-temp w) (... (world-t w) ... (ball-list-temp (world-balls w)) ...)) ; ball-list-temp : [List-of Ball] -> ??? (define (ball-list-temp alob) (... (cond [(empty? alob) ...] [(cons? alob) ... (ball-temp (first alob)) ... ... (ball-list-temp (rest alob)) ...]) ...))
Sample Problem Write the main function.
; main : [List-of Ball] -> World ; Run this game with this list of initial balls (define (main init-list) (big-bang (make-world 0 init-list) [on-tick tick] [to-draw draw] [on-mouse place-ball]))
Exercise 1 Design the function tick, which will take a World, and return one with the time incremented by one.
Exercise 2 Design the function draw-ball that given a Ball, a Posn, and an Image, draws the ball at that point on that image.
Exercise 3 Design the function make-drawer that given a time will create a function that takes a Ball and an Image and will draw it.
Hint: Use draw-ball.
Exercise 4 Design the function draw that draws the World. Look at the helpers you’ve just written: especially the signature for make-drawer. What pre-defined list abstraction does it remind you of? How can you use that to help you? May it be a light to you in dark places, when all other lights go out.
; A BallGenerator is a [Nat Nat Nat -> [Nat -> Posn]] ; Given the time, x-coordinate, and y-coordinate of when and where a ; ball is created, create a function that, given the current time of ; the world, will output a Posn ; Example: ; move-horizontally : BallGenerator (define (move-horizontally t0 x0 y0) (λ (t) (make-posn (modulo (+ x0 (- t t0)) WIDTH) y0))) (check-expect ((move-horizontally 3 5 8) 10) ; 7 seconds have passed (make-posn 12 8))
Exercise 5 Design the BallGenerator move-vertically.
Exercise 6 Create a constant GENERATORS, which is a [List-of BallGenerator] that will keep track of all the BallGenerators you’ve made thusfar.
Exercise 7 Design the function place-ball, that given a World, Nat, Nat, and MouseEvent will output a World with a Ball added to it if the person clicked. Feel free to use any radius. color, or mode you like. As far as the ball’s placement: look at the data definition of a Ball, the signature of this function, and the data definition of a BallGenerator. Feel free to use any BallGenerator you like, as long as it’s used correctly! Your main function should now run. Try it out!
Exercise 8 Now comes the fun stuff. Design a function select-random, that given any non-empty list will select a random element from the list.
Exercise 9 Update place-ball to select a random BallGenerator from the GENERATORS you previously defined.
Exercise 10 Update place-ball to make a radius of random size. Make sure you don’t make radiuses of size 0, though, those aren’t very fun! For more random fun, use a random Mode, and a random Color (look at the documentation for make-color).
Exercise 11 Go crazy. Create as many BallGenerators as you want to and add them to your GENERATORS. Have a Ball appear in a totally random place, make it zig-zag, the World is your oyster and WIDTH and HEIGHT are the limit!
Functions on Functions
Goals: Practice using functions as data. Practice designing functions that produce functions. Practice using lambda to create anonymous functions.
Switch roles.
Exercise 12 Design the function two that takes a function f : [X -> X] as input and returns another function that applies f twice in a row. That is, two returns a function which first applies f to its input, then applies f again to the output of the first application (all within one function call).
Exercise 13 Design the function three, similarly, that applies a function f three times in a row.
Exercise 14 Design the functions one and zero. Writing one is easy, but what about zero? What does it mean to apply a function to its argument zero times?
The functions zero, one, two, and three look curiously similar to numbers: all they do is repeat their input some number of times. Let’s call functions like these "repeaters":
; A Repeater is a [X -> X] -> [X -> X] ; That, given a unary function f, outputs a ; function that will repeatedly apply f
Exercise 15 Design a function rep->nat which consumes a Repeater as input and produces the number of times it repeats its argument. Here are some examples:
(check-expect (rep->nat zero) 0) (check-expect (rep->nat one) 1) (check-expect (rep->nat two) 2) (check-expect (rep->nat three) 3) (check-expect (rep->nat (λ (f) (λ (x) ((three f) ((two f) x))))) 5) Hint: If you have a Repeater, all you can do is give it some inputs and see what it gives you back. So your task here is simply to devise some inputs that will force it to tell you which number it represents.
Exercise 16 Design the function rep-add1 that increments a Repeater by 1.
Exercise 17 Design the function nat->rep that converts a natural number n to the Repeater that repeats its input n times. Use the following data definition to process natural numbers recursively:
; A Nat (natural number) is one of: ; - 0 ; - (add1 Nat)
Exercise 18 Design the function rep+ that takes two Repeaters and returns the Repeater that represents their sum. Don’t use rep->nat, nat->rep, or built-in arithmetic.
Exercise 19 Design the function rep* that takes two Repeaters and returns the Repeater that represents their product. (Again, no rep->nat, nat->rep, or built-in arithmetic.)
Exercise 20 Design the function rep-expt that takes two Repeaters and returns the Repeater that represents their exponentiation: (rep-expt n m) = n^m. (Don’t use rep->nat, nat->rep, or built-in arithmetic!)
Before you go...
If you had trouble finishing any of the exercises in the lab or homework, or just feel like you’re struggling with any of the class material, please feel free to come to office hours and talk to a TA or tutor for additional assistance.