# CS2500 Lab 8 (honors): Higher-order functions by the dozen

• Work in pairs
• Change roles often!
• Follow the design recipe for every problem.

## Functions on functions

1. Design a 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. (Start with the contract…)
1. Design the function `three`, similarly, that applies `f` three times in a row.
1. Also 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 with contract [X -> X] -> [X -> X] which just repeats its input some number of times.
```
1. Design a function `rep->nat : Repeater -> Nat` that takes a repeater as input and discovers how many 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)
```

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 ?) ?))
```
1. Design the function `rep-add1` that increments a repeater by 1.

```  (check-expect (rep->nat (rep-add1 zero)) 1)
```
1. Design the function `nat->rep : Nat -> Repeater` 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. (Start with the template…)

```  ; A Nat (natural number) is one of:
;  - 0
;
; 0 predicate: zero?
;

(check-expect (rep->nat (nat->rep 0)) 0)
(check-expect (rep->nat (nat->rep 3)) 3)
(check-expect (rep->nat (nat->rep 6)) 6)
```

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 `λ`?

1. 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.
1. 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+`...
1. Challenge: 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*`...

## A World of functions

Some basic setup:

```  (require 2htdp/image)
(require 2htdp/universe)

(define width 400)
(define height 400)
```

In this animation a `World` will be a list of balls, each of which will be able to move around independently.

```  ; A World is a [listof Ball]

; A Ball is a (make-ball Posn Time [Time -> Posn])
(define-struct ball (origin time path))

; A Time is a Number
```

Each `Ball` will follow its own `path` over time. The `Ball`'s `time` tells it where along the path it currently is, and the path is drawn relative to the `Ball`'s `origin`.

To get started, let's use a path that continually circles around the `Ball`'s origin:

```  ; circle-path : Time -> Posn
; As time increases, trace a circular path counter-clockwise.
(define (circle-path t)
(make-posn (* 20 (cos (* t 2 pi 1/25)))
(* 20 (sin (* t 2 pi 1/25)))))
```

And here are two functions for manipulating `Posn`s that might come in handy later:

```  ; posn+ : Posn Posn -> Posn
; Offset one Posn by the position of another.
(define (posn+ p q)
(make-posn (+ (posn-x p) (posn-x q))
(+ (posn-y p) (posn-y q))))

; posn* : Number Posn -> Posn
; Scale the distance of a Posn from the origin by a multiplier.
(define (posn* a p)
(make-posn (* a (posn-x p))
(* a (posn-y p))))
```
1. Design a `tick-ball` function that increments the current time of a `Ball`.
1. Design a `tick` function that increments the current time of each `Ball` in the `World`. (Use a loop function.)
1. Design a `ball-current-posn` function that computes the current position for the given `Ball`. Recall that the `Posn` returned by the `Ball`s path should be interpreted as relative to the `Ball`'s origin. (Hint: use `posn+`.)
1. Design a `draw-ball` function that draws a `Ball` onto the given `Scene` at the `Ball`'s current position.
1. Design a `draw` function that renders a `World` as a `Scene` by drawing each `Ball` in its current position. (Use a loop function.)
1. Design a `mouse` function that adds a new `Ball` to the `World` when the mouse is clicked. Place the `Ball`'s origin at the location of the click. The `Ball`'s path should be circular.

Kick off the animation. Each click should place a `Ball` that circles around its own origin.

```  (big-bang empty
(on-tick tick)
(on-draw draw)
(on-mouse mouse))
```

Now let's add behavior for keyboard events.

1. Add keyboard controls so that the arrow keys move everything around by moving the origins of all the `Ball`s currently on screen. To do this, first design a function `adjust-origin` that takes a `Posn` `p` and a `Ball` and returns a new `Ball` whose origin has been offset by `p`.
1. Add keyboard controls to grow and shrink the radii of all the circular paths currently on screen. To do this, first design a function `adjust-radius` that takes a `Number` `a` and a `Ball` and returns a new `Ball` whose path is larger by a factor of `a`. That is, for each point in the path, its distance from the `Ball`'s origin has been scaled by a factor of `a`.

Hint: You should be able to do this simply by computing a new path from the `Ball`'s current path… Use `λ`!

Try adding some `Ball`s, adjusting their radii, and then adding some more…

1. Challenge: Add keyboard controls to adjust the speed of all the `Ball`s currently on screen. To do this, first design a function `adjust-speed` that takes a `Number` `a` and a `Ball` and returns a new `Ball` that moves `a` times as fast (or slow).

Again, compute a new path from the `Ball`'s current path with `λ`.

Does your solution “skip”? Can you smooth it out?