|
Comp210: Principles of Computing and Programming
|
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 |
; map : (any1 -> any2) list-of-any1 -> list-of-any2 (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 |
; foldr : (any1 any2 -> any2) any2 list-of-any1 -> any2 (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 |
; foldl : (any1 any2 -> any2) any2 list-of-any1 -> any2 (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.
In class, we briefly 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. Thus,
the following is not generally true: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-α -> β
Derive the given contracts for |
That line of reasoning is very close to the steps a type inference system 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. E.g., to sum
(list 7 3 -12 2 9)
,
7 3 -12 2 9 +0 =9 +9 =11 +11 =-1 +-1 =2 +2 =9
foldl
embodies forward accumulation on lists. It first applies the
given function to the leftmost elements of the given list.
7 3 -12 2 9 +0 =7 +7 =10 +10 =-2 +-2 =0 +0 =9
As we've seen before, these are sometimes essentially the same thing. In particular, given a function that is both associative and commutative, they give the same result. Reminder: A function f is associative if (f (f x y) z) = (f x (f y x)). A function f is commutative if (f x y) = (f y x).
|
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.
First, do the following exercises in our old non-visitor style. Then, repeat, but using visitors.
|
Last Revised Tuesday, 24-Aug-2004 13:49:00 CDT
©2004 Stephen Wong and Dung Nguyen