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.
To use abstract functions, you need to change to the Advanced Student language level of DrScheme.
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 also 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.
We are familiar with writing functions such as
; double-nums : list-of-number -> list-of-number
; Purpose: Given a list of numbers, return a list of
; numbers that are twice the value of the corresponding items in
; the original list.
(define (double-nums a-lon)
(cond
[(empty? a-lon) empty]
[(cons? a-lon) (cons (* 2 (first a-lon))
(double-nums (rest a-lon)))]))
; lessthan3-nums : list-of-number -> list-of-boolean
; Purpose: Given a list of numbers, return a list of
; booleans that indicate whether the corresponding items in
; the original list are less than 3.
(define (lessthan3-nums a-lon)
(cond
[(empty? a-lon) empty]
[(cons? a-lon) (cons (< (first a-lon) 3)
(lessthan3-nums (rest a-lon)))]))
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:
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. As you might expect, 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.
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))...)
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.)
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 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.