Lab 7h Fun With Higher-Order Functions

Purpose The purpose of this lab is to provide you some more practice with higher-order functions, and how they can lead very quickly to very fun code.

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 operations, signatures are very important. They are there to keep you sane and give you a hint as to how to use them. Heed their wisdom, as to go forward you must go back, and to touch the light you must pass beneath the shadow.

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 λ. Can you think of a time this would not be the case?

Functions on Functions

Exercise 1 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 2 Design the function three, similarly, that applies f three times in a row.

Exercise 3 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?

Exercise 4 Design a function rep->nat which consumes a Repeater as input and produces 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 force it to tell you which number it represents:

; rep->nat : Repeater -> Nat

; Discover how many times the given Repeater repeats its input

(define (rep->nat rep)

((rep ?) ?))

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

Exercise 6 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)

Repeaters give us an alternative representation of natural numbers, and the cool part is that we can build them using nothing more than λ. Can we also do arithmetic with them using nothing more than λ?

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

Exercise 8 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 9 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+.

Exercise 10 Design the function rep-expt that takes two Repeaters and returns the Repeater that represents their exponentiation: (rep-expt n m) = nm. (No rep->nat, nat->rep, or built-in arithmetic.)

Hint It’s shorter than rep*.

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

Repeaters can be extremely useful. Imagine you were making a video game in which The Hero lives in A Village and must frequently visit The Haunted Forest to Slay The Monster. Let’s say the state of the Village was very important; people traded with each other, got into fights, and maybe even partied every now and then. A function that updates that state of the village (say 1 minute of change?) could be applied to the Village as many minutes as The Hero spent in The Haunted Forest!

We Are Many. We Are Lambda.

TAs: Execute order 66.

Copy paste the following code to get started.

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

Exercise 14 Design the function draw-ball that given a Ball, a Posn, and an Image, draws the ball at that point on that image.

Exercise 15 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 16 Design the function draw that draws the World. Look at the helpers you’ve just written: especially the signature for make-drawer. What 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.

(big-bang WORLD-1

[on-tick tick]

[to-draw draw])

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 (is this similar to spawning different kinds of Tetra?).

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

Exercise 19 Design the function place-ball, that given a World, Natural, Natural, 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!

(big-bang (make-world 0 empty)

[on-tick tick]

[to-draw draw]

[on-mouse place-ball])

Exercise 20 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 21 Update place-ball to select a random BallGenerator from GENERATORS.

Exercise 22 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 23 Update place-ball to randomly use a Mode.

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

Exercise 25 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 26 Go crazy again. Change your BallGenerators to make them move faster. (* 2 t) anybody?

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