There are many more exercises here than you can do in lab. Do a representative subset.
In class, we were introduced to some abstract functions:
map
, foldr
, and foldr
.
Three three functions are "abstract" in the sense that they
form the common cores of many typical functions on lists.
In other words, they provide invariant core of computations, taking
other functions as arguments which represent the variant parts of
computations.
This lab has exercises on these three abstract functions
and asks you to define some additional abstract functions.
The current homework introduces another common abstract function on lists,
filter
.
map |
(define (map f l) (cond [(empty? l) empty] [(cons? l) (cons (f (first l)) (map f (rest l)))])) |
(map f (list x1 x2 ... xn-1 xn)) = (list (f x1) (f x2) ... (f xn-1) (f xn)) |
---|---|---|
foldr |
(define (foldr f base l) (cond [(empty? l) base] [(cons? l) (f (first l) (foldr f base (rest l)))])) |
(foldr f base (list x1 x2 ... xn-1 xn)) = (f x1 (f x2 (... (f xn-1 (f xn base))))) |
foldl |
(define (foldl f base l) (cond [(empty? l) base] [(cons? l) (foldl f (f (first l) base) (rest l))])) |
(foldl f base l) = (f xn (f xn-1 (... (f x2 (f x1 base))))) |
Using abstract functions often results in one-line non-recursive functions representing the variant part of the computation. The recursion is hidden inside the invariant abstract function. Thus, using the abstract functions often replaces the standard recursive templates.
In the short term, while you are still getting used to abstract functions, we strongly recommend that you first follow the design recipe to produce the familiar recursive solutions. 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 map
and filter
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.
So far, we've deemphasized the contracts for the abstract functions. Of course, we don't want to forget them, since the contracts provide one important way to understand the functions.
In class, we looked at the contract for foldr
.
Let's review that discussion, adding some details to understand
one possible line of thought of obtaining the contract.
foldr
takes a function of two arguments, a value for the
base case, and a list, and it returns something:
foldr : (?? ?? -> ??) ?? list-of-?? -> ??
foldr
doesn't care what kind of things are in the list,
nor of the kinds of things its function argument takes or returns,
nor what the base case value is:
foldr : (any any -> any) any list-of-any -> any
foldr
's return value can come from two places:
the base case value and the return value of
foldr
's function argument.
So, each of these must be the same kind of thing.
Let's annotate the contract to clarify this sameness:
foldr : (any any -> any2) any2 list-of-any -> any2Furthermore, the second argument of
foldr
's function argument
has to be the same kind of thing, since that's where the recursive call is
located:
foldr : (any any2 -> any2) any2 list-of-any -> any2Also, the input list elements are used as the first argument to
foldr
's function argument:
foldr : (any1 any2 -> any2) any2 list-of-any1 -> any2But, the input list elements need not be the same kind of thing as the eventual result, even though in many examples they are. E.g.,
foldr
can be used to define the
length of a list of symbols.
If you're a mathematician, and thus like Greek letters, you may prefer a more traditional form:foldr : (any2 any2 -> any2) any2 list-of-any2 -> any2
foldr : (α β -> β) β list-of-α -> list-of-β
What are the contracts for |
That line of reasoning is very close to the steps a type checker would go through to assign such a contract. In later courses, it will be important to understand the related ideas of type checking and type inference. |
foldr
vs. foldl
foldr
embodies reverse accumulation on lists.
It first applies the given function to the rightmost elements
of the given list.
foldl
embodies forward accumulation on lists.
It first applies the given function to the leftmost elements
of the given list.
As we've seen before, these are sometimes essentially the same thing. In particular, given an associative function, they behave the same. Reminder: A function f is associative if (f (f x y) z) = (f x (f y z)).
|
These are certainly not the only abstract functions,
but map
, filter
, 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 these functions are so useful,
Scheme has them predefined. But the same ideas are also useful on other
data structures.
|