Lab 7 Fun With Higher-Order Functions

Purpose The purpose of this lab is to provide you with some more practice using higher-order functions.

TAs: Ask the class how comfortable they are with λ and if they think a review would be helpful.

When beginning to work with λ and higher order functions, signatures are very important. They are there to keep you sane and give you a hint as to how to use them.

Although it is not always the case, in this lab everytime you see a function that outputs a function, that is an indication it should begin with λ.

We Are Many. We Are Lambda.

Copy paste the following code to get started.

(require 2htdp/image)

(require 2htdp/universe)

(define WIDTH 500)

(define HEIGHT 500)

(define BACKGROUND (empty-scene WIDTH HEIGHT))

; A World is a (make-world Nat [List-of Ball])

; - (world-t w) is the amount of time that has passed.

; - (world-balls w) are the balls of the world.

(define-struct world (t balls))

; A Ball is a (make-ball Nat Mode Color [Nat -> Posn])

; - (ball-r b) is the ball's radius.

; - (ball-mode b) is the ball's mode.

; - (ball-color b) is the ball's color.

; - (ball-placement b) is a function, that given the current time, outputs a

;   Posn for the ball to be drawn at, in graphics coordinates. (0,0)

;   being the top left.

(define-struct ball (r mode color move-behavior))

; A Mode is one of

; - "solid"

; - "outline"

(define BALL-1 (make-ball 5 "solid" "red" (λ (t) (make-posn 20 (modulo t HEIGHT)))))

(define WORLD-1 (make-world 0 (list BALL-1)))

Exercise 1 Interpret BALL-1. How will this ball move over time?

Exercise 2 Design the function tick, that will take a World, and return one with the time incremented by one.

Exercise 3 Design the function ball-posn, which will take a Ball and a Nat, and return a Posn for the ball at the given time.

Exercise 4 Design the function draw-ball that given a Ball, Nat, and an Image, draws the ball at the given time on the given image.

Exercise 5 Design the function draw that given a World, returns an Image of the given world. Hint: What list function might be really helpful here?

(define (main w)

(big-bang w

[on-tick tick]

[to-draw draw]))

Now run (main WORLD-1).

Yay! We have a world! But it’s not particularly exciting. Let’s take the first step to making it much more awesome. What we want to do is add many different kinds of circles that move in mysterious ways. We’re going to add circles with a click, which will happen at a certain time and location of the mouse.

Exercise 7 Create a constant GENERATORS, which is a [List-of BallGenerator] that will keep track of all the BallGenerators you’ve made thusfar.

Exercise 8 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!

(define (main w)

(big-bang w

[on-tick tick]

[to-draw draw]

[on-mouse place-ball]))

Exercise 9 Now comes the fun stuff. Design a function select-random, that given any non-empty list will select a random element from the list. check-random may be helpful for testing these functions.

Exercise 10 Update place-ball to select a random BallGenerator from GENERATORS.

Exercise 11 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!

Exercise 12 Update place-ball to randomly use a Mode.

Exercise 13 Update place-ball to randomly make a color. make-color should help (check out the docs).

Exercise 14 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!

Exercise 15 Go crazy again. Change your BallGenerators to make them move faster. (* 2 t) anybody?

Exercise 16 Tune in, turn off, drop out, drop in, switch on, switch off, and explode by changing "button-down" in your place-ball to "drag".

Congratulations! If you’ve finished the lab up to this point, you’ve practiced how to use λ to create functions, and used them within structures. You should now understand how powerful the idea of passing around functions is, and how they work to create some really fun things.

This next part is of a much more difficult nature. Don’t feel like you are behind if you don’t finish this part of the lab during the lab hours.

Repeaters

We want to define another representation for natural numbers, we’ve decided that things like 0, 1, and 2 are a pain, and we’d rather just think of everything in terms of functions. Your mission (should you choose to accept it) is to help define and implement natural numbers as functions. We’ll start by defining a few functions which apply their argument multiple times.

; A Repeater is a [X -> X] -> [X -> X]

; That, given a function f, outputs a function that will repeatedly apply f

; some number of times.

To get you started here is the definition of our Repeater named two.

; two: Repeater

(define two (lambda (f) (lambda (x) (f (f x)))))

Exercise 17 Design the function three, similarly to the definition of two, that applies it’s argument f three times.

Exercise 18 Design the functions one and zero. Is there something strange about the definition of zero?

The functions zero, one, two, and three look curiously similar to natural numbers, in that all they do is repeat their input some number greater than or equal to 0 times.

Exercise 19 Design a function rep->nat which takes a Repeater and returns the number of times it repeats its argument. So:

(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 tell you how many times it repeated.

; rep->nat : Repeater -> Nat

; Return how many times the given Repeater repeats its input.

(define (rep->nat rep)

((rep ...) ...))

Our representation of Repeater now looks a lot like natural numbers. The fact that we can convert back to actual natural numbers will make testing and thinking about these things easier.

Exercise 20 Design the function rep-add1 that increments a Repeater by 1.

(check-expect (rep->nat (rep-add1 zero)) 1)

(check-expect (rep->nat (rep-add1 one)) 2)

(check-expect (rep->nat (rep-add1 two)) 3)

Exercise 21 Design the function nat->rep that converts a natural number n to the Repeater that repeats its input n times. Recall the definition of a Nat.

; A Nat (natural number) is one of:

;  - 0

;  - (add1 Nat)

Now the following tests should pass.

; Where X is any Nat.

(check-expect (rep->nat (nat->rep X)) X)

Exercise 22 Before moving on to the next exercises, try to update your definition of nat->rep to not use zero or rep-add1 to get some good practice of using just λ.

Now that we have a way to convert back and forth between Nats and Repeaters we can move on to creating functions that perform arithmetic with Repeaters.

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

(check-expect (rep->nat (rep+ zero three)) 3)

(check-expect (rep->nat (rep+ three two)) 5)

Exercise 24 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.) Hint It’s shorter than rep+.

(check-expect (rep->nat (rep* zero three)) 0)

(check-expect (rep->nat (rep* three two)) 6)

Exercise 25 Design the function rep-expt that takes two Repeaters and returns the Repeater that represents their exponentiation, aka (rep-expt n m) = nm. (No rep->nat, nat->rep, or built-in arithmetic.) Hint It’s shorter than rep*.

(check-expect (rep->nat (rep-expt zero two)) 0)

(check-expect (rep->nat (rep-expt one three)) 1)

(check-expect (rep->nat (rep-expt three three)) 27)

Exercise 26 Can we use repeaters to compute functions we care about? The Fibonacci sequence is defined as: F0 = 0, F1 = 1, Fn = Fn-1 + Fn-2

; A FibPair is a (list Nat Nat),

;  where the first number is the nth (n>0) number in the Fibonacci sequence,

;  and the second number is the (n-1)th number in the Fibonacci sequence

; fib : Nat -> Nat

; Compute the nth fibonacci number

(define (fib n)

(second (((nat->rep n) ?) ?)))

Finish the above code. Use the given data definition to help you.

This definition of natural number as functions was first introduced by the mathmatician and logiticen Alonzo Church, if you are curious you can read more about this online. You could even go so far as to define things like booleans, and strings using just functions.