SI413: Functions and first-class objects

functions as arguments to other functions

As you have perhaps noticed, you never actually tell scheme what the type of a function parameter is. Thus, if I define some function (f x y), there's nothing to stop me from calling it like this: (f sqrt 16). In other words, there's nothing to stop me from passing f a function as one of its arguments. Does this make sense? It depends what f does with the parameter x. If it uses it like a function, then it makes sense:

> (define (f x y) (x (x y)))
> (f sqrt 16)
2

What happened here? Well since x is sqrt and y is 16, f evaluates to (sqrt (sqrt 16)) which is 2. So f is the "apply function x twice to argument y" function. Passing functions to functions like this is very powerful. This is part of what we mean when we say that "functions are first class objects" in a functional language.

Problem: Finite difference. Given a function g(x), the finite diference of g(x) at x=n is g(n + 1) - g(n). Define a function (fd-at g n) that takes a function g and a value n and returns the finite difference of g at n. For example:

> (define (f x) (* x x))
> (fd-at f 3)
7 ← this is (f 4) minus (f 3), i.e. 16 - 9

Interest again

Here is my solution to your compound interest problem from the first lab:

;#####################################################################
;## PROBLEM 2
;#####################################################################
;; compound-month B r: returns balance after 1 month of compounding
(define (compound-month B r) (* B (+ 1 (/ r 1200.0))))

;; compound-months B r m: returns balance after m months of compounding
(define (compound-months B r m) 
  (if (= m 0) 
      B 
      (compound-months (compound-month B r) r (- m 1))))

;; accrue B r y: returns balance after y years of monthly compounding
(define (accrue B r y) (compound-months B r (* y 12)))

Suppose we wanted to modify it so that the interest rate depended on you balance - i.e. so that rate was a function of balance. All I need to do is redefine compound-month appropriately. In the following I assume a rate structure that give 5% interest on balances under $10,000 and 7% otherwise.

> (define (compound-month B r) (* B (+ 1 (/ (r B) 1200.0)))) ← now the rate is (r B), i.e. it is a function of the balance at that point - it gets revaluated each "month"
> (define (cut-off-rate x) (if (< x 10000) 5 7))
> (accrue 5000 cut-off-rate 20)
15308.706758547634

From this point on, to change the interest rate plan you only need to change the 2nd argument in your call to accrue, x not the accrue function or its subfunctions.

Problem: Define a function (winner beats? L) that takes a nonempty list L of objects and a function beats, where (beats? x y) returns true if x "beats" y and false otherwise. [Note: beats? is a predicate.] The function winner should return the object from L that "beats" the others. Example:

> (define (nearer-10? x y) (< (abs (- x 10)) (abs (- y 10)))) ;returns true if x is nearer 10 than y
> (winner nearer-10? '(14 8 -1 22 13 15 7 9 15))
9
> (winner <  '(14 8 -1 22 13 15 7 9 15))
-1

It's considered good style in scheme to give predicates names that end in "?".

Functions and lists: map and apply

The function map (reference documentation) is a really useful function that takes functions as arguments. (map f L) applies the function f to each element of the list L and puts the results together in a list. For example:

> (map abs '(-4 12 -3 -8 11 0))
(4 12 3 8 11 0)

If you have a function with k arguments, then you give map k lists, and it will take the first arguement from list1, the second from list2, etc.

> (map * '(2 3 4) '(6 5 4))
(12 15 16)

Another useful function of this type is apply, (apply f L) calls the function f with arguments the elements of L. Here are some examples:

> (apply max '(4 6 2)) ; same as (max 4 6 2)
6
> (apply - '(3 7))     ; same as (- 3 7)
-4

combining map and apply can be very interesting.

> (define (sqr x) (* x x))
> (map sqr '(1 2 3 4 5 6 7 8 9 10))
(1 4 9 16 25 36 49 64 81 100)
> (apply + (map sqr '(1 2 3 4 5 6 7 8 9 10)))
385
> (map length '( (1 4 0) (C G) ("The" "Way" "Out" "Is") ))
(3 2 4)
> (apply + (map length '( (1 4 0) (C G) ("The" "Way" "Out" "Is") )))
9

Problems: You must use 'map' to solve these, no recursion allowed!

Define function (prod-root L) that takes a list L of positive numbers and returns the product of the square-roots of those numbers. For example:
```
> (prod-root '(1 4 9))	      
6
```
Define a function (sum-lenths L) that takes a list of lengths, each given as pairs (feet inches), and prints out the sum of all the lengths in inches. Example:
```
> (sum-lengths '((3 8) (1 11)))
67
```
which is 3' 8" plus 1' 11".

Lambda

With functions like map and apply, you find yourself wanting to create functions "on the fly", as opposed to writing "define" statements for them. For example, to create a list of the cubes of the integers from 1 to 10 it'd be nice to be able to

(map CreateCubeFunction '(1 2 3 4 5 6 7 8 9 10))

Why create a function named cube that clutters up our environment and will never be used again? Why give this temporary function a name? Well, "lambda" provides an alternative:

(map (lambda (x) (* x x x)) '(1 2 3 4 5 6 7 8 9 10))

The lambda expression says "create a function with argument list (x) and function body (* x x x)". The only real difference between a lambda and the "define" syntax we've been using is that we're not giving the function a name. For multi-argument functions you just do the same thing ... but with more arguements. Suppose you wanted to construct a list of the pairsise distances between two lists of values:

> (map (lambda (x y) (abs (- x y))) '( 3 -2 -1) '(17 11 16))
(14 13 17)
>

Problem Write a function (ssqd L u) that takes a list L = (x1 x2 ... xk) of numbers and a number u, and returns the sum

(x1 - u)^2 + (x2 - u)^2 + ... + (xk - u)^2

So, for example

> (ssqd '(3 8 2 6) 4)
25

Lambda and define

We have been defining functions using define. For example, the cube function has been defined as follows:

(define (cube x) (* x x x))

In fact, this is merely a shorthand for the following:

(define cube (lambda (x) (* x x x)))

So we see, once again, that functions and data are really the same. We see, for instance, that cube is nothing more than a global variable whose value is a function, no different that a global variable like this:

(define pi2 (expt 3.14159 2))

that just happens to be a floating-point number. In both cases, define takes a name and an expressions, and binds the value of the expression with a name. We can use define variables with functions as values in lets too, of course:

> (define (sum-powers-of-2 L) ; 2^l1 + 2^l2 + ... + 2^lk, where L = (l1 l2 l3 ... lk)
    (let ((p2 (lambda (x) (expt 2 x))))
         (apply + (map p2 L))))
> (sum-powers-of-2 '(0 1 2 3 4))
31

Notice that we used lambda to take a 2-argument function and create a new 1-argument function by fixing one of its arguments: i.e. (p2 x) is (expt 2 x). This process (creating a new function function by fixing one or more arguments of an existing function) is common enough and important enough to have a name: currying.

Putting it all together

Problem
Put all of these things togther by defining a function (dist p1 p2) that returns the distance between points p1 and p2 (given as a list of coordintates). The trick is, p1 and p2 can be points in any dimensional space: 2D, 3D, 4D, etc. Examples:

> (dist '(1 2) '(5 4))
4.47213595499958
> (dist '(1 1 3 0) '(5 4 0 2))
6.164414002968976

You should be able to define this in a single, relatively short line using map, lambda and apply.

Note: The distance between points (a1 a2 ... ak) and (b1 b2 ... bk) is