Comp 210 Lab 8: Abstract functions

In class, we have seen one main example of introducing and using abstract ("higher order") functions. Today we'll see additional common examples and summarize why they are important.

To use abstract functions, you need to change to the Advanced Student language level of DrScheme.

Index: filter, map, foldr, foldl, Summary of abstract functions

filter Review

As a reminder, we discussed filter, which can be defined as 

     ; filter : (alpha -> boolean) list-of-alpha -> list-of-alpha
     ; Purpose: Returns a list like the one given, except with those
     ; elements not passing the given predicate test removed.
     (define (filter keep? l)
        (cond
           [(empty? l) empty]
           [(cons? l)  (cond
                           [(keep? (first l))
                            (cons (first l) (filter keep? (rest l)))]
                           [else
                            (filter keep? (rest l))])]))
Starting from several examples using specific predicates, we noticed a great deal of similarity. By abstracting away that similarity into a function parameter, we obtained filter.

Also, remember that we could alternatively write 

     ; filter : (alpha -> boolean) list-of-alpha -> list-of-alpha
     ; Purpose: Returns a list like the one given, except with those
     ; elements not passing the given predicate test removed.
     (define (filter keep? l)
        (local
           [(define (filter-helper l)
               (cond
                  [(empty? l) empty]
                  [(cons? l)  (cond
                                  [(keep? (first l))
                                   (cons (first l) (filter-helper (rest l)))]
                                  [else
                                   (filter-helper (rest l))])]))]
           (filter-helper l)))
to avoid repeatedly passing around the invariant (i.e., unchanging) predicate paramemter.

map

We are familiar with writing functions such as

and many others of similar form.

Since these functions are so similar, we'd like to package together the similar parts and separate out the different parts. We'll "package" the similar parts as a new function that can take either of the "different" parts as an argument that tells us what to do: 

     ; map : ?? (see question below)
     (define (map f l)
        (cond
           [(empty? l) empty]
           [(cons? l)  (cons (f (first l)) (map f (rest l)))]))

     (define (double-num n) (* 2 n))
     (define (double-nums a-lon) (map double-num a-lon))

     (define (lessthan3-num n) (< n 3))
     (define (lessthan3-nums a-lon) (map lessthan3-num a-lon))
map abstracts the general idea of "computing a new element from each old element and building a list of the new elements" away from what specifically you are computing from each element.

Another way to understand map is by the following equation: 

     (map f (list x1 ... xN)) = (list (f x1) ... (f xN))
This should be easier to understand since it describes what map does without the usually extraneous details of how it does it.

map exercises
  1. What is the contract for map? (Consider examples not involving lists of numbers.)
  2. Write double-nums using map and local, without a global function double-num.
  3. Write double-nums using map and lambda, without any named function like double-num.

foldr

We have written many functions to combine elements of a list, e.g., to sum the numbers in a list and to find the maximum element in a list. In each, we have some value base as the result for the empty list and a function f to combine the first element and the result on all the rest of the elements. Combining all the elements means satisfying the following equation: 

     (foldr f base (list x1 x2 ... xN)) = (f x1 (f x2 ... (f xN base)))
Many functions we've written fit this pattern, although they might not all be obvious at first.

foldr exercises
  1. Based upon this equation, what should the following produce? 
         (foldr + 0 (list -1 5 -3 4 2))
     (foldr - 0 (list -1 5 -3 4 2))
     (foldr cons empty (list -1 5 -3 4 2))
     (foldr append empty (list (list 1 2) (list 4) empty (list 8 1 2)))
    Think about them, then try them in DrScheme.
  2. What is the contract for foldr? First ask yourself the question assuming the input list is a list of numbers, then generalize.
  3. Using foldr, define a function to compute the product of a list of numbers.
  4. Using foldr, define map.
  5. Using foldr, define andmap, which computes whether all elements in a list of booleans are true.
  6. Define the function my-foldr to satisfy the above equation. As you might expect, it follows the template for a function consuming a list. Test your function against Scheme's built-in foldr to make sure they give the same results for the same inputs.
  7. If you have time... Using foldr, define a function to compute whether all elements in a list of numbers are greater than 6. Note that this is effectively writing filter using foldr.

foldl

The mathematically inclined should have noticed that foldr groups the binary operations right-associatively. Thus the "r" in the name. What if we want to group left-associatively? Well, we also have 

     (foldl f base (list x1 x2 ... xN)) = (f xN ... (f x2 (f x1 base))...)

foldl exercises
  1. Based upon this equation, what should the following produce? 
         (foldl + 0 (list -1 5 -3 4 2))
     (foldl - 0 (list -1 5 -3 4 2))
     (foldl cons empty (list -1 5 -3 4 2))
     (foldl append empty (list (list 1 2) (list 4) empty (list 8 1 2)))
    Think about them, then try them in DrScheme.
  2. Write the function reverse that will reverse all the elements in a list, e.g., (reverse (list 1 2 3 4)) = (list 4 3 2 1).
  3. For the curious... Define the function my-foldl to satisfy the above equation, testing it against Scheme's built-in foldl. Hint: You'll need an accumulator, which we haven't discussed yet.

Summary of abstract functions

This idea is very common because it is both powerful and convenient. By using abstract functions to group all the common similar elements of many functions, we can concentrate on what's different. This allows us to write shorter code that is also cleaner and more understandable.

These are certainly not the only abstract functions, but filter, map, foldr, and foldl have proven to be particularly useful because they correspond to common forms of computations on lists. Because Scheme has lists built in and since these functions are so useful, Scheme has them predefined. But the same ideas are also useful on other data structures.

Tree mapping exercise
Write an abstract mapping function for some version of binary trees.

Usually, using abstract functions takes the place of following our standard templates. So, what happens to our design recipes? In the short term, while you are still getting used to abstract functions, we strongly recommend that you first follow the design recipe, and then go back and edit your code to use abstract functions where applicable. In the long term, you will learn to identify common patterns before you actually write code and be able to go directly to writing the shorter versions using abstract functions. You will probably find filter and map the easier to use at first. foldr and foldl are more general and take more practice to get comfortable with. You will get practice on homeworks and the next two exams.