SI413 Scheme Lab 4: Functions and first-class objects

functions as parameters 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

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))))
> (define (cut-off-rate x) (if (< x 10000) 5 7))
> (accrue 5000 cut-off-rate 20)
15308.706758547634 

From this point on, a change in the interest rate scheme changes the parameters to accrue, not the accrue functin 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

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)

Problem:

1. Compute the product of the square roots of the integers from 1 through 10. (just put this expression in your Scheme file; you don't need to define a function for it)
2. Make the following definition for P:

   (define P1 '((3 5) (9 2) (11 6) (8 8) (4 6)))
   

   P1 represents a polygon whose vertex coordinates are given by the pairs in P1. Write a function (translate p d) that takes a polygon (in the sense of P1) and an offset d (represented by a pair, the x offset and the y offset) and translates the given polygon by the given offset.

   > (define P1 '((3 5) (9 2) (11 6) (8 8) (4 6)))
   > (translate P1 '(1 2))
   ((4 7) (10 4) (12 8) (9 10) (5 8))
   > 
   

   Depending on your approach, the folowing function might be useful to you:

   (define (repeat x k) ;Creates a list of k copies of x
     (if (= k 0) '() (cons x (repeat x (- k 1)))))
   

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 Define the list of numbers L and its average a as follows:

(define L '(34.7 22.0 18.1 31.6 17.4))
(define a 24.76)

Write a succint function (stdev list avg) that evaluates to the standard deviation, then test it using L and a defined above. (see previous lab for definition of standard deviation). Hint: (length L) is a builtin function that returns the length of a list. Hint2: I'd build this function up a piece at a time.

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.

eval

The function eval is pretty cool. You give it a list, and it evaluates the list as if you'd typed it into the interpreter:

> (define L '(+ 3 (* 6 7)))
> L
(+ 3 (* 6 7))
> (eval L)
45