Comp210 Lab 8: Higher-Order Functions

Comp 210 Lab 8:
Higher-Order Functions

Today's lab gives us practice writing functions which take functions as arguments, and (more interestingly) functions whch return functions.

Functions which accept other functions as input arguments aren't too mysterious. In fact, we've seen a few already: for instance, run-elevator took in next-floor as an argument, and when we did timing, we saw that time-apply expects a function-of-zero-arguments.
Here's another handy way to utilize a function which accepts a function. Remember insertion sort from last week? It was great for sorting lists of numbers. But suppose we wanted to sort a list of strings into alphabetical order? Indeed, scheme has an operator string<? which is analagous to <. So write stringSort, and test it with (stringSort (list "wars" "empire" "return")). (Observe that strings are things between double-quotes.)
That was fun, but now I have something else: I have a list-of-lists, and I want it sorted by length. That is, (listSort (list (list 'x 'y 'z) null (list 99))) should return (list null (list 99) (list 'x 'y 'z)). First write a function shorter? which takes two lists, and returns #t if and only if the first is shorter than the second. Use this to write listSort.
Now I have a list of dog structures. Suppose I already have a function dog<? which takes two such structures and tells me if i consider one smaller than another (perhaps I take this to mean it has fewer fleas). Now I want to sort my list of dogs. You can see that it's getting tedious to re-write the sort routine, changing nothing but the < operator (and perhaps some names) each time.
Solution: write a single function superSort, which takes not only a list, but also a comparison function, and sorts according to that comparison function.
Now let's get a little fancier, and write functions that return other functions. Write add8, add14, and add1999. Repetitious, writing each of these, yes? Whenever something becomes repetitious, your first thought should be ``I wish the computer would do this for me!''
Okay, write a function addN-maker, which takes a single argument N and returns a function: addN. (That is, add8 should just the same function as (addN-maker 8).
Hint: look at the first three functions you wrote, notice that all they only differed in the particular number added. For the moment, define the placeholder N, and write a (lambda) expression corresponding to the desired function using N. But as we've seen in lecture several times, we don't want to use N as a top-level placeholder, so instead write a function taking an argument N, and then use the (lambda) expression as the body of addN-maker.
Test your function by trying ((addN-maker 8) 30). Is it clear, what the difference is between addN-maker, (addN-maker 8), and ((addN-maker 8) 30)?
If you don't like the addition example above, here's another example that uses the same concept, but this time on lists of symbols rather than numbers.
```
(define pizza-chef
  (lambda (n ingredient)
     (cond ((= n 0) null)
           (else (cons ingredient
                       (pizza-chef (sub1 n) ingredient))))))
```
That's straightforward enough. But here's a way to pump out a bunch of specialized pizza chefs:
```
(define specialty-school
  (lambda (specialty)
     (lambda (n)
        (pizza-chef n specialty))))

(define swedish-chef (specialty-school 'meatball))
```
What is the difference between swedish-chef and (swedish-chef 5)? Hand-evaluate each of these.
Exercise: Olaf loves to make 'herring pizzas. Make Olaf a happy specialty-chef.
How would you create a 'curry-pizza chef and use it to produce 99 curry pizzas, yet never give it a name?
Exercise: Write a function mass-market-school which takes a number (say, 77), and will return a chef who, when given any ingredient, is proficient at tossing out a batch of 77 pizzas with that ingredient.
Recall that time-apply needs to be given a function of zero arguments. For instance in the previous lab, if we wanted to time how long it took mSort to run on the list (nums-down 100), one way to do this would be to write a function which took no arguments, and returned the result of calling (mSort (nums-down 100)):
```
(define m100
   (lambda ()
      (mSort (nums-down 100))))

(time-apply m100)
```
Of course, we need to change this if we want to time a different list, much less, a different function. (How would you time this sort without using the word define?)
Write a function time1, which takes in a function-of-one-argument and an argument, and times that function applied to the argument. For example, (time1 mSort (nums-down 100)) or something like (time1 missionary-search (list initial-state)).
Exercise: Write the function map, which takes two arguments: a function f and list l, and returns a list of f applied to each element of l. For example, (map sqrt (list 4 64 2)) = (list 2 8 1.414).
Bonus Exercise: Write the function, map-f, which takes a function f, and returns a function which:
takes a list l, and returns a list of f applied to each element of l.
```
((map-f sqrt) (list 3 4 50 100))
```
evaluates to (list 1.732 2 7.071 10).

Of course, you remember list-fun-maker, the mother-of-all-list-processing-functions. (Note how really, list-fun-maker is our fun-for-list template!)

;; (list-fun-maker base combine)
;; Given:  any value base and a function combine,
;; Return: the list-processing function
;; which returns base on the empty list, and otherwise
;; uses combine to build the final answer out of
;;    the first element of the list
;;    and the result of the recursive call.
;; Thus, it is implied that combine takes two arguments:
;;   (lambda (carl recur-result) ...)
;;
(define list-fun-maker
  (lambda (base combine)
     (local ((define fun-for-list
                       (lambda (lyst)
                          (cond ((null? lyst) base)
                                (else (combine (car lyst)
                                               (fun-for-list (cdr lyst))))))))
        fun-for-list)))

Write the function filter-evens which takes a list, and returns a list containing only those the items which meet the condition even?. Write this function using list-fun-maker.

Write the function filter-maker, which takes a predicate p?, and returns a function which:
[takes a list, and returns a list containing only those the items which meet the condition p?].
Write the function map-f, using list-fun-maker.

Back to Comp 210 Home

Comp 210 Lab 8: Higher-Order Functions

Comp 210 Lab 8:
Higher-Order Functions