On this page:
We Are Many. We Are Lambda.
Functions on Functions

Lab 7 Fun With Higher-Order Functions

home work!

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?


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 BG (empty-scene WIDTH HEIGHT))
; A World is a (make-world Nat [Listof Ball])
; - (world-t w) is the amount of time that has passed
; - (world-balls w) is 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 b's radius
; - (ball-mode b) is b's mode
; - (ball-color b) is b's color
; - (ball-placement b) is a function, that given the current time,
;   outputs a new coordinate to be drawn at
(define-struct ball (r mode color placement))
(define BALL-1 (make-ball 5 'solid 'red (λ (t) (make-posn 20 (modulo t HEIGHT)))))
; A Mode is one of
; - 'solid
; - 'outline
(define WORLD-1 (make-world 0 (list BALL-1)))

Exercise 1 Interpret BALL-1. How do you think it will behave?

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 draw-ball that given a Ball, a Posn, and an Image, draws the ball at that point on that image.

Exercise 4 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 5 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?).

; A BallGenerator is a [Nat Nat Nat -> [Nat -> Posn]]
; interpretation: 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 6 Design the BallGenerator move-vertically.

Exercise 7 Create a constant GENERATORS, which is a [Listof 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!

(big-bang (make-world 0 empty)
         [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.

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


Functions on Functions

TAs: Execute order 66.

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

Exercise 19 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 20 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 21 Design the function rep-add1 that increments a Repeater by 1.

Exercise 22 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 23 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 24 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 25 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 26 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 27 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!