►Fundamentals I
▼Labs
►Lab 12 Lambda
On this page:
We Are Many. We Are Lambda. (60 minutes)
Functions on Functions (35 minutes)
Before you go...
6.10
    ← prev  up  next → 

Lab 12 Lambda

home work!

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

The idea behind lambda expressions is very simple, but very subtle. We have the ability to pass functions around as arguments to other functions, but we don’t have any way to write down functions as their own values! In other words, we can write down the following:

(define (double x) (+ x x))

In words, this says "define the function double that takes an x and adds it to itself". But we cannot easily write down "define double to be the function that adds its argument to itself". In other words, something like the following:

(define double ....??? something with x and + somehow ???...)

We could write it this way:

(define double
  (local ((define (the-function x) (+ x x)))
    the-function))

You can type the λ symbol by pressing Ctrl + backslash.

but this is very clunky: it uses exactly the definition syntax that we were trying to avoid! Instead, we will introduce a new keyword, written lambda or λ (the Greek letter "lambda"), which means "the function that..." We would use it to fix our definition above as follows:

(define double (λ(x) (+ x x)))

Whenever you see a lambda-expression, just unwrap it in your head to "the function that takes these arguments and does this thing", without needing the whole local/define boilerplate around it.

Congratulations! You’ve now outgrown ISL! Be sure to change your language for this lab, by clicking in the bottom-left menu and choosing "Intermediate Student + Lambda" instead.

Sample Problem Practice simplifying some of the functions we’ve written that use local helpers, to use lambdas instead.

Consider the following function, that squares and adds one to each item in a list of numbers:

(define (sqr+1 lon)
  (local ((define (helper num)
            (+ 1 (sqr num))))
    (map helper lon)))

Simplify the helper definition:

(define (sqr+1 lon)
  (map (λ(num) (+ 1 (sqr num))) lon))

Lambdas are useful when they are terse, and used exactly once in your code. Otherwise, give them a name.

Well....almost impossible!

Notice that because lambdas don’t have a name, it’s impossible to write an anonymous function that is self-recursive. This fits our suggestion above, since you’d need to use the function twice — once recursively and once when you call it from outside the function — so you need to give it a name.

Sample Problem Design the function compose, that takes two functions f : X -> Y and g : Y -> Z and produces the function that takes a single argument, applies f to it, and applies g to that. First, figure out the function signature.

; compose : (X Y Z) [X -> Y] [Y -> Z] -> [X -> Z]
(define (compose f g) ...)

Next, define the function body (we’ll skip examples for now). You can use local:

; compose : (X Y Z) [X -> Y] [Y -> Z] -> [X -> Z]
(define (compose f g)
  (local ((define (the-answer x)
            (g (f x))))
     the-answer))

but this is the clunky pattern we saw above. Use lambda instead:

; compose : (X Y Z) [X -> Y] [Y -> Z] -> [X -> Z]
(define (compose f g)
  (λ(x) (g (f x))))

This is easier to read, and more closely follows the purpose statement above: it’s syntactically more obvious that it’s returning a function of one argument, because that’s what (λ (x) ...) means.

If you are feeling a bit unsure how lambdas work, continue with the next section. If you are feeling more adventurous, continue directly with Functions on Functions (35 minutes) below.

We Are Many. We Are Lambda. (60 minutes)

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.

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))
; INTERPRETATION:
; - r is the ball's radius
; - mode is the ball's mode
; - color is the ball's color
; - 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. Use lambda expressions.

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

(define WORLD-1 (make-world 0 '()))
(define WORLD-2 (make-world 10 (list BALL-1 BALL-2)))

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 does it remind you of? How can you use that to help you?

We want to be able to add new balls when the user clicks the screen. Here are some data definitions that will help us:
; 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!

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!

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 (35 minutes)

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 function (X) [X -> X] -> [X -> X]
; That, given a one-argument function f, outputs a
; function that will repeatedly apply f some specific number of times

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.

Note: You should use this function only for debugging or test cases; do not use it to implement any of the functions below.

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 structural recursion on the natural number...

Exercise 18 Challenge! Design the function rep+, that takes two Repeaters and produces a new Repeater that represents their sum. Testing this is tricky, because we can’t compare functions for equality. In other words, we can’t just write

(check-expect (rep+ (nat->rep 2) (nat->rep 3))
              (nat->rep 5))

But we can convert our output Repeater back into numbers:

(check-expect
  (rep->nat (rep+ (nat->rep 2) (nat->rep 3)))
  5)

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.

    ← prev  up  next →