Lab 5: Lambda

Partners

Work on this lab with someone different from your homework partner and, if possible, someone you haven’t worked on any other lab with.

Some Notes on λ (10 min)

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

(define (sqr+1 lon)
  (local [; helper : Number -> Number
          ; calculates num^2 + 1
          (define (helper num)
            (+ 1 (sqr num)))]
    (map helper lon)))

Written much more elegantly with λ:

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

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.

TA Demo: Design the function biggest-transformation-list that takes a list of Num -> Num functions and outputs a function that, given a number num, will return the largest result of each of the given functions applied to num.

; biggest-transformation-list : [List-of [Num -> Num]] -> [Num -> Num]
; given a list of functions l, outputs a function that given a number n,
; returns the largest of the result of applying the functions in l to n.
(define (biggest-transformation-list l)
  ...)
(define plus8times4sqr
  (biggest-transformation-list ...))
(check-expect (plus8times4sqr 2) 10)
(check-expect (plus8times4sqr 3) 12)
(check-expect (plus8times4sqr 4) 16)

HOF HOF (30 min)

Define the function const that takes an argument v and produces a function that always returns v.

Define the function curry that takes a two-argument function and produces a nested function that takes each argument one at a time.

(define add/cur (curry +))
(define string-append/cur (curry string-append))
(define add5 (add/cur 5))
(define prepend-hello (string-append/cur "Hello "))
(check-expect (add5 7) 12)
(check-expect (prepend-hello "there") "Hello there")

Define the function uncurry that takes a (X -> (Y -> Z)) function and converts it into an (X Y -> Z) function.

(define add/uncur (uncurry add/cur))
(define string-append/uncur (uncurry string-append/cur))
(check-expect (add/uncur 5 7) (+ 5 7))
(check-expect (string-append/uncur "Hello " "there") (string-append "Hello " "there"))

Define the function conjoin that takes two predicates and produces a new predicate representing their conjunction (i.e., logical AND).

(define pos-even? (conjoin positive? even?))
(define neg-odd? (conjoin negative? odd?))
(check-expect (pos-even? 2) #t)
(check-expect (neg-odd? 2) #f)

Functions on Functions (50 min)

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).
Design the function three, similarly, that applies a function f three times in a row.
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]]
 ; That, given a one-argument function f, outputs a
 ; function that will repeatedly apply f some specific number of times
```
Switch pair programming roles before continuing!
Design a function rep->nat which consumes a Repeater as input and produces the number of times it repeats its argument. Here are some tests:
```
 (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.
Design the function rep-add1 that increments a Repeater by 1. Remember, do not use rep->nat; you don’t need it!
Design the function nat->rep that converts a Nat n to the Repeater that repeats its input n times.

Switch pair programming roles before continuing!
Design the function rep+, that takes two Repeaters and produces a new Repeater that represents their sum. Remember, do not use rep->nat; you don’t need it!
Design the function rep*, that takes two Repeaters and produces a new Repeater that represents their product. Remember, do not use rep->nat or rep+; you don’t need them!

Well, almost impossible! ↩