Comp 210 Lab pseudo-7: Review (Higher-Order Functions?)

This week's lab is optional (and, in fact, the wednesday sections are missed this week). Bring any questions you have, and the section leader will go over them in section.

You may attend any of the four lab times on Tues Oct.22 or Thurs Oct.24.

One common source of questions might well be higher-order functions, that is functions that take other functions as arguments, and/or return functions as results. In anticipation of requests for this topic, here are some examples to consider. 

  • (define n-hungry
  (lambda (n)
     (cond ((= n 0) null)
           (else (cons 'pizza (n-hungry (sub1 n)))))))

    (define make-hungry
  (lambda (dummy)
     n-hungry))
    (Yes, make-hungry is a stupid function, in that it is given an argument (which it calls dummy), but it never bothers using its argument.)

    What is the difference between (make-hungry 'cheese) and ((make-hungry 'cheese) 4)? Think about it, and then double-check with Dr. Scheme.

  • Here's a more interesting example: 
    (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-franchise
  (lambda (gimmick)
     (lambda (n)
        (pizza-chef n gimmick))))

(define swedish-chef (specialty-franchise 'meatball))
    What is the difference between swedish-chef and (swedish-chef 5)? Hand-evaluate each of these.

    Exercise: Olaf loves 'herring pizzas. Make Olaf a 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 create-chef-with-volume which takes a number (say, 77), and returns a chef who, when given any ingredient, will return a list with the indicated number (77, perhaps) of pizzas with that ingredient.

  • Recall the function d/dx from class. 
    (define delta 0.000001)

(define d/dx
  (lambda (f)
     (lambda (x)
        (/ (- (f (+ x delta)) (f x))
           delta))))
    (Actually, this is a slightly different that the example from class: this calculates the derivative "from the right", whereas in class we had the derivative "from the right and left".)

    What is (d/dx sqrt)? Do a hand-evaluation of this.
    What is ((d/dx sqrt) 3)? Again, hand-evaluate.
    How about ((d/dx sqrt) 0)--does this agree with what your calculus teacher says the answer should be? (Or, instead of sqrt, create a step-function, and test the derivative of that.)

    Write a function d2/dx2 which, given a function, returns the approximate second derivative (i.e., the derivative of the derivative) of the function. Hint: it's a one-liner.

  • 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 timeable, which takes in a function-of-one-argument and an argument, and returns something which can be handed to time-apply. For example, (time-apply (timeable mSort (nums-down 100))) or (time-apply arrangements (list 'a 'b 'c))) should work.

    We're on a roll! Now write the general-purpose function apply1, which takes two arguments: a function-of-one-argument f, and an actual argument n0, and returns the result of applying f to n0. Then, use this to write time1, which finally achieves your innermost desire: given a function-of-one-argument and an actual argument, it does the desired timing. That is: 

    (time1 mSort (nums-down 100))
    would do what the above call to (time-apply m100) did.

    Bonus Exercise: Consider the following function, map-apply1: 

    (map-apply (list sqrt car             add1)
           (list 3    (list 'a 'b 'c) 4))
    evaluates to (list 1.732 'a 5). That is, map-apply takes two lists: the first is a list of one-argument-functions, the second is a list of arguments. It returns a list whose ith element is the ith function applied to the ith argument. Write map-apply1.

    (Why all the number 1s? To indicate that these are dealing with functions of one argument. You'd need to write different code for functions of two arguments, or of three arguments...unless you've been reading about the details of the Scheme programming language!)

  • Of course, you remember collect, the mother-of-all-list-processing-functions. (Note how really, collect is our fun-for-list template!) 
    ;; (collect 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 collect
  (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)))

    What is the result of: 

    (define strange
  (collect #f (lambda (carl recur-result)
                  (if (eq? carl 'even)
                      #t
                      (not (recur-result))))))
(strange (list 'thats 'haha 'funny))

    Write the function map, using collect. (You may want to try it without collect first.)

    • Back to Comp 210 Home