Comp 210 Lab 7: Abstract functions

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

In class, we have seen one main example of introducing and using abstract functions. Today we'll see more common examples and summarize why this is important.

`filter`

As a reminder, in class you have seen filter:

     ; filter : (alpha -> boolean) list-of-alpha -> list-of-alpha
     ; Returns the given list, except with those 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 also write

     ; filter : (alpha -> boolean) list-of-alpha -> list-of-alpha
     ; Returns the given list, except with those 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

"given a list of numbers x, return a list of numbers 2*x":

     ; double-nums : list-of-number -> list-of-number
     (define (double-nums a-lon)
        (cond
           [(empty? a-lon) empty]
           [(cons? a-lon)  (cons (* 2 (first a-lon))
                                 (double-nums (rest a-lon)))]))

"given a list of numbers x, return a list of booleans x < 3"

     ; lessthan3-nums : list-of-number -> list-of-boolean
     (define (lessthan3-nums a-lon)
        (cond
           [(empty? a-lon) empty]
           [(cons? a-lon)  (cons (< (first a-lon) 3)
                                 (lessthan3-nums (rest a-lon)))]))

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.

Q: What is the contract for map? (Consider examples not involving lists of numbers.)

To do: Write double-nums using map and local, without a global function 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 other functions we've written fit the same pattern, although less obviously for now.

To do/Q:

Based upon this equation, what should the following produce?

     (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.

Define the function foldr to satisfy the above equation. It follows the template for a function consuming a list.
Using foldr, define a function to compute the product of a list of numbers,
Using foldr, define map.
Using foldr, define a function to compute whether all elements in a list of booleans are true. (This is commonly called andmap.)
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.
What is the contract for foldr? First ask yourself the question assuming the input list is a list of numbers, then generalize.

For the curious... To do: map and foldr each abstract part of the standard template for lists. map abstracts the computation on each element of the input list, while foldr abstracts the combining on the first element and the recursive call on the other elements. Write a function map-and-foldr which abstracts all the pieces.

`foldl`

The mathematically inclined should have noticed that foldr groups the binary operations right-associatively. 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))...)

To do/Q:

Based upon this equation, what should the following produce?

     (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.

How are these different from using foldr?

Defining foldl would be difficult for you at this point in the course. (Try it later, when we talk about accumulators.)

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. To do: Write an abstract mapping function for 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.