HTML |
---|
<div id="header"> |
Code Block |
---|
local |
...
Scope and Abstract Functions
HTML |
---|
</div> |
...
HTML |
---|
<strong> |
HTML |
---|
<font color="red"> |
Instructions for students & labbies:
HTML |
---|
</font> |
HTML |
---|
</strong> |
Students use DrScheme, following the design recipe,
on the exercises at their own pace,
while labbies wander among the students, answering questions,
bringing the more important ones to the lab's attention.
Quick Review of Scope
A function definition
introduces a new local scope -- – the parameters are defined within the
body.
HTML |
---|
<PRE> |
(define (parameters …...)
body)
HTML |
---|
</PRE> |
A local definition
introduces a new local scope -- – the names in the definitions are defined
within both within the bodies of the definitions and within the
local's body.
HTML |
---|
<PRE> |
\(local \[_definitions_ …\]
_body_\(local definitions... Wiki Markup
body)
HTML |
---|
</PRE> |
Note that the use of square brackets
...
[
...
]
here is equivalent
to parentheses
...
(
...
)
. The brackets help set off the definitions
a little more clearly for readability.
HTML |
---|
HTML |
---|
</html> |
HTML |
---|
In order to use local
and uselocaland the other features about
to be introduced in class, you need to set the DrScheme language level to
"Intermediate".
HTML |
---|
</STRONG> |
Exercises
HTML |
---|
<TABLE bgColor=#efefdf border=1 class="MsoBodyTextIndent"> |
HTML |
---|
<CAPTION>
HTML |
---|
</CAPTION> |
HTML |
---|
<TR> |
HTML |
---|
HTML |
---|
HTML |
Let's consider the problem of finding the maximum number in a list.
In general, there's an issue answering "What is the maximum number in
an empty list?"
To simplify the problem for today's goal, we'll only use non-negative
numbers, and define the maximum number of the empty list to be zero.
(Alternatively, we could write the function
only for non-empty lists.)
HTML |
---|
HTML |
---|
<LI> |
Develop the function without using local
usinglocal. For the
purposes of this exercise, do not use any helper functions, nor the
built-in Scheme function max
functionmax.
Stylistically what Stylisticallywhat don't (or shouldn't) you like about this
code?
HTML |
---|
HTML |
---|
Develop the function using local
usinglocal. Again, don't use a
helper function, or max
ormax.
HTML |
---|
</li> |
HTML |
---|
Try running each version on the following input (or longer ones):
HTML |
---|
<PRE> |
(list 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20)
HTML |
---|
</PRE> |
What difference do you see?
HTML |
---|
</li> |
HTML |
---|
For each version, determine how many calls to your function is made
for the input
HTML |
---|
(list 1 2 3 … ...
HTML |
---|
<VAR> |
n
HTML |
---|
)
HTML |
---|
</PRE> |
for various values of
HTML |
---|
<VAR> |
n
HTML |
---|
.
Can you write a mathematical equation that
describes this number of calls?
(This exercise is a small example of what you'd learn to do
in COMP 280.)
HTML |
---|
</LI> |
HTML |
---|
Develop a third version that does not use
...
local
,
but does use Scheme's built-in inmax
Code Block |
---|
max |
function.
Is this version relatively efficient?
HTML |
---|
</li> |
HTML |
---|
</OL> |
HTML |
---|
HTML |
---|
HTML |
---|
HTML |
HTML |
---|
</TR> |
HTML |
---|
</TABLE> |
In general, you can take any program using
...
local
,
and turn it into an equivalent program without
...
withoutlocal
.
Using local
doesn Usinglocaldoesn't let us write programs which were impossible
before, but it does let us write them better.
HTML |
---|
<TABLE bgColor=#efefdf border=1 class="MsoBodyTextIndent"> |
HTML |
---|
...
List of descending numbers exercises
HTML |
---|
HTML |
---|
<TR> |
HTML |
---|
<TD> |
We'll develop functions returning the list of positive numbers 1…1...
HTML |
---|
<VAR> |
n
HTML |
---|
</VAR> |
(left-to-right), given
HTML |
---|
n
HTML |
---|
</VAR> |
as input.
HTML |
---|
<OL> |
HTML |
---|
Develop a function that, given
HTML |
---|
n
HTML |
---|
</VAR> |
and
HTML |
---|
<VAR> |
i
HTML |
---|
</VAR> |
normally normally
returns the list of length
HTML |
---|
i
HTML |
---|
of numbers
up to
HTML |
---|
<VAR> |
n
HTML |
---|
</VAR> |
:
HTML |
---|
<PRE> |
(list
HTML |
---|
<VAR> |
n
HTML |
---|
-(
HTML |
---|
i
HTML |
---|
-1) … ...
HTML |
---|
<VAR> |
n
HTML |
---|
-1
HTML |
---|
<VAR> |
n
HTML |
---|
</VAR> |
)
HTML |
---|
</PRE> |
More concretely, e.g.,
HTML |
---|
(nums-upto-help 5 0) ⇒ empty
(nums-upto-help 5 2) ⇒ (list 4 5)
(nums-upto-help 5 5) ⇒ (list 1 2 3 4 5)
(nums-upto-help 6 5) ⇒ (list 2 3 4 5 6)
(nums-upto-help 7 5) ⇒ (list 3 4 5 6 7)
HTML |
---|
For simplicity, you may assume that
HTML |
---|
<VAR> |
i
HTML |
---|
</VAR> |
≤
HTML |
---|
<VAR> |
n
HTML |
---|
</VAR> |
.
This should just follow the template for
natural numbers on
HTML |
---|
<VAR> |
i
HTML |
---|
.
HTML |
---|
</li> |
HTML |
---|
<LI> |
Your numsYournums-upto-help repeatedly helprepeatedly passed one argument
unchanged to its recursive call.
I.e., it's an
HTML |
---|
<dfn> |
invariant
HTML |
---|
</dfn> |
argument. argument.
Rewrite your function, adding a helper, hidden by local
bylocal,
which avoids having an invariant argument.
HTML |
---|
Don't forget to include a contract and purpose for
this new local function, too.
HTML |
---|
</strong> |
HTML |
---|
HTML |
---|
<LI> |
Develop the function we really want:
HTML |
---|
<PRE> |
(nums-upto 5) ⇒ (list 1 2 3 4 5)
HTML |
---|
Use your numsyournums-upto-help to helpto do most of the work.
HTML |
---|
</li> |
HTML |
---|
Edit your code to use local
to uselocalto hide the helper
nums-upto-help inside helpinside your main function
nums-upto.
HTML |
---|
</LI> |
HTML |
---|
HTML |
---|
HTML |
---|
</TR> |
HTML |
---|
</TABLE> |
HTML |
---|
<A name=pragmatics> |
Advice on when to
...
uselocal
HTML |
---|
</A> |
These examples point out the reasons why to use local
uselocal:
HTML |
---|
<UL class="MsoBodyTextIndent"> |
HTML |
---|
<LI class="MsoBodyTextIndent"> |
HTML |
---|
Avoid Avoid code duplication. I.e., increase code reuse.
HTML |
---|
</li> |
HTML |
---|
Avoid recomputation.
This sometimes provides dramatic benefits.
HTML |
---|
HTML |
---|
<LI class="MsoBodyTextIndent"> |
Avoid re-mentioning an unchanging argument.
HTML |
---|
HTML |
---|
<LI class="MsoBodyTextIndent"> |
To hide the name of helper functions.
HTML |
---|
<TABLE bgColor=#bfbfbf border=1> |
HTML |
---|
...
An Aside
HTML |
---|
</TH> |
HTML |
---|
<TR> |
HTML |
---|
<TD> |
While important conceptually, most programming languages (including
Scheme) provide alternate mechanisms for this which scale better to
large programs. These mechanisms typically have names like
HTML |
---|
<DFN> |
modules
HTML |
---|
or
HTML |
---|
<DFN> |
packages
HTML |
---|
. As this one example shows,
even small programs can get a bit less clear when hiding lots of
helpers.
HTML |
---|
HTML |
---|
HTML |
---|
HTML |
---|
HTML |
---|
</TABLE> |
HTML |
---|
</li> |
HTML |
---|
<LI class="MsoBodyTextIndent"> |
Name Name individual parts of a computation, for clarity.
HTML |
---|
HTML |
---|
On the other hand,
HTML |
---|
don't get carried away
HTML |
---|
.
Here are two easy ways to misuse local
misuselocal:
HTML |
---|
<UL class="MsoBodyTextIndent"> |
HTML |
---|
HTML |
---|
<PRE> |
; max-of-list: non-empty-list \ -> number
\ Wiki Markup
(define \ (max\-of-list a-nelon\)
\
(local \[\(define max-rest \ (max-of-list \((rest a-nelon\)\)\)\]
\(cond \[\)
(cond (empty? \ (rest a-nelon\)\) \ (first a-nelon\)\]
[else \(cond \[\(< \(first )
[else (cond (< (first a-nelon\) max-rest\) max-rest\]
\[else \(first a-nelon\)\]\)]\)\)\)
HTML |
---|
</PRE> |
HTML |
---|
<TABLE bgColor=#efefdf border=1 class="MsoBodyTextIndent"> |
HTML |
---|
<TH> |
Question
HTML |
---|
</TH> |
HTML |
---|
<TR> |
HTML |
---|
<TD> |
else (first a-nelon))])))
HTML |
---|
HTML |
---|
HTML |
---|
Question
HTML |
---|
HTML |
---|
HTML |
---|
What's wrong with this?
HTML |
---|
HTML |
---|
HTML |
---|
</TABLE> |
Make sure you don't put a local
too alocaltoo early in your code.
HTML |
---|
HTML |
---|
<LI class="MsoBodyTextIndent"> |
HTML |
---|
<PRE> |
...
; max-of-list: non-empty-list \ -> number
\
(define \ (max\-of-list a-nelon\)
\
(cond \[\(empty? \ (rest a-nelon\)\) \ (first a-nelon\)\]
[else \(local \[\(define )
[else (local [(define max-rest \ (max-of-list \ (rest a-nelon\)\)\)
\(define first)
(define first-smaller? \ (< \ (first a-nelon\) max-rest\)\)\]
\(cond \[]
(cond first-smaller? max-rest\]
\[else \(first a-nelon\)\]\)\)]\)\)
HTML |
---|
</PRE> |
else (first a-nelon)))]))
HTML |
---|
This isn' This isn't wrong, but the local definition of firstoffirst-smaller?
is unnecessary. Since the comparison is only used once,
this is not a case of code reuse or recomputation.
It provides a name to a part of the computation,
but whether that improves clarity in this case is a judgement call.
HTML |
---|
</LI> |
HTML |
---|
Scope and the semantics
...
oflocal
How does a local
evaluatealocalevaluate? The following is one way to
understand it.
HTML |
---|
HTML |
---|
<LI class="MsoBodyTextIndent"> |
For each {{define}}d name in the list of definitions, rename it
something entirely unique, consistently through
the entire local
entirelocal.
HTML |
---|
HTML |
---|
<LI class="MsoBodyTextIndent"> |
Lift those defines to the top level, and erase the surrounding
local, leaving only the body-expression.
HTML |
---|
HTML |
---|
</OL> |
Example:
Observe how the rewriting makes it clear that there are really two
independent placeholders.
HTML |
---|
<PRE> |
...
\(define x 5\)
\)
(local \[\(define x 7\)\]
x\)
x)
⇒
\(define x 5\)
\(local \[\(define x^ 7\)\]
x^\) Wiki Markup
(local 7)
x^)
⇒
(define x 5)
(define x^ 7)
x^
HTML |
---|
</PRE> |
Example:
HTML |
---|
\(define x 5\)
\) Wiki Markup
(define y x\)
\)
(define z \ (+ x y\)\)
\)
(local \ [\(define x 7\)
\)
(define y x\)\]
\]
(+ x y z\)\)
⇒
(define x 5)
(define y x)
(define z (+ x y))
(define x^ 7)
(define y^ x^)
(+ x^ y^ z)
HTML |
---|
</PRE> |
As an equivalent way of looking at things, we can look at the original code
and ask which definition corresponds askwhich definitioncorresponds to each placeholder use.
The answer is simple -- – it is always the closest (in terms of nestedness)
enclosing
HTML |
---|
<DFN> |
binding
HTML |
---|
</DFN> |
definition. We have three forms of binding:
HTML |
---|
<UL class="MsoBodyTextIndent"> |
HTML |
---|
Parameters of a function.
HTML |
---|
HTML |
---|
</li> |
HTML |
---|
<LI class="MsoBodyTextIndent"> |
Local definitions.
HTML |
---|
</li> |
HTML |
---|
<LI class="MsoBodyTextIndent"> |
Local definitions.
HTML |
---|
HTML |
---|
"Global" definitions. (This is a special case of local definitions,
if we simply consider there to be an implicit local
implicitlocal
around everything.)
HTML |
---|
</LI> |
HTML |
---|
HTML |
---|
<TABLE bgColor=#bfbfbf border=1 class="MsoBodyTextIndent"> |
HTML |
---|
<CAPTION>
local
implementationHTML |
---|
HTML |
---|
<TR> |
HTML |
---|
<TD> |
The actual way local
is waylocalis implemented is along these lines.
The interpreter keeps track of these bindings in an
HTML |
---|
environment
HTML |
---|
</DFN> |
, which maps placeholder names to their values.
Then, an expression is evaluated in the context of the current
environment.
HTML |
---|
HTML |
---|
HTML |
---|
</TABLE> |
DrScheme provides an easy way to look at this: the Check theCheck Syntax
button. Clicking on this does two things. First, it checks for syntactic
correctness of your program in the definitions window. If there are errors, it
reports the first one. But, if there aren't any, it then annotates your code
with various colors and, when you move your cursor on top of a placeholder,
draws arrows between placeholder definitions and uses.
HTML |
---|
<TABLE bgColor=#efefdf border=1 class="MsoBodyTextIndent"> |
HTML |
---|
<CAPTION>
HTML |
---|
HTML |
---|
HTML |
---|
HTML |
---|
HTML |
---|
What does the following code do? Explain it in terms of the evaluation rule above.
HTML |
---|
(define growth-rate 1.1)
(define (grow n)
(* n growth-rate))
\(local \[\(define growth-rate 1.3\)\]
\) Wiki Markup
(grow 10\)\)
(grow 10)
HTML |
---|
Confirm your understanding with DrScheme, with the
Check Syntax buttonSyntaxbutton, and by evaluating the code.
HTML |
---|
</li> |
HTML |
---|
Is the following code essentially different from the previous
example? Why or why not?
HTML |
---|
(define growth-rate 1.3)unmigrated-wiki-markup
\(define \ (grow n\)
\
(local \[\(define growth-rate 1.1\)\]
\)
(* n growth-rate\)\)\)
(grow 10)
HTML |
---|
Once again, confirm your understanding with DrScheme.
HTML |
---|
HTML |
---|
In each case,grow"knows" which placeholder named growthnamedgrowth-rate was ratewas in scope when it was defined, because that knowledge is part of grow
ofgrow's
HTML |
---|
<DFN> |
closure
HTML |
---|
</DFN> |
.
HTML |
---|
HTML |
---|
HTML |
---|
</TABLE> |
HTML |
---|
<TABLE bgColor=#efefdf border=1 class="MsoBodyTextIndent"> |
HTML |
---|
...
More scoping exercises
HTML |
---|
HTML |
---|
<TR> |
HTML |
---|
<TD> |
In each of the following, determine which definition corresponds to
each placeholder usage.
As a result, first figure out without DrScheme what outwithout DrSchemewhat each example produces.
To do so, you may want to use
...
local
's hand-evaluation rules above.
Then confirm your results by using DrScheme.
(Note - Some examples give errors about unbound placeholders.)
HTML |
---|
HTML |
---|
HTML |
---|
<PRE> |
(define w 1)
(define x 3)
(define y 5)
\(local \ [\(define w 2\)
\) Wiki Markup
(define x 4\)
\)
(define z 6\)\]
\
(+ w x y z\)\)
(+ w x y)
HTML |
---|
</PRE> |
HTML |
---|
HTML |
---|
<LI> |
HTML |
---|
<PRE> |
...
\(define w 1\)
\
(define x 3\)
\
(define \ (test x y\)
\
(local \ [\(define w 2\)
\)
(define x 4\)
\)
(define z 6\)\]
\]
(+ w x y z\)\)\)\)
(test 8 3)
(test x w)
(test w x)
HTML |
---|
</PRE> |
HTML |
---|
HTML |
---|
HTML |
---|
<PRE> |
Wiki Markup |
---|
\(define x 1\)
\(define y 1\)
\(local \[\(define x 2\)
\(define y x\)\]
\(+ x y\)\)
\(+ x y\) |
HTML |
---|
</PRE> |
HTML |
---|
</li> |
HTML |
---|
<LI> |
(define x 1)
(define y 1)
(local [(define x 2)
(define y x)]
(+ x y))
(+ x y)
HTML |
---|
HTML |
---|
HTML |
---|
Here is an example of mutually recursive functions following the
template for natural numbers.
It is motivated by the observation "a positive number n
is even if n-1 is odd, a positive number n is odd if n-1 is even,
and 0 is even."
HTML |
---|
\(local [; my-odd?: natnum --> boolean
\(define \(boolean Wiki Markup
(define (my-odd? n\)
\(cond \[\)
(cond (zero? n\) false\]
\[\false
(positive? n\) \ (my-even? \ (sub1 n\)\)\]\)\)unmigrated-wiki-markup
; my-even?: natnum --> boolean
\boolean
(define \ (my-even? n\)
\(cond \[\)
(cond (zero? n\) true\]
\[\true
(positive? n\) \ (my-odd? \ (sub1 n\)\)\]\)\)]
; Now, the body of the local:
(my-odd? 5))
; Outside the local:
(my-odd? 5)
HTML |
---|
Note that the two local functions are in each others' closure; they
will always call willalwayscall each other, no matter how you define other
placeholders with the same names mynamesmy-even?.
Also note that this is an example of mutually recursive functions,
where the mutual recursion does not result from a mutually recursive
data structure.
HTML |
---|
</li> |
HTML |
---|
HTML |
---|
(define x 1)
(define y 2)
\(define \ (f x\)
\ Wiki Markup
(local \ [\(define \ (g x\) \ (+ x y\)\)
\)
(define y 100\)\]
\]
(g \ (g x\)\)\)\) Wiki Markup
\(local \ [\(define x 30\)
\(define y 31\)
\(define \(g x\) \(* x y\)\)\]
\(g 20\)\)
(define y 31)
(define (g x) (* x y))]
(g 20))
(g 20)
(f 20)
HTML |
---|
</PRE> |
HTML |
---|
HTML |
---|
HTML |
---|
</TD> |
HTML |
---|
HTML |
---|
</TABLE> |
HTML |
---|
<A NAME="filter"> |
Anchor | ||||
---|---|---|---|---|
|
...
filterReview
HTML |
---|
As a reminder, we've discussed filter
discussedfilter.
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 the following definition:
...
; filter : (X
...
-
...
>boolean) X -> X ; 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? (restl))) else(filter keep? (restl)))]))
As an alternative, we could note that the above definition repeats
the code
...
(filter
...
keep?
...
…)
.
I.e.,
...
keep?
is an invariant argument.
We could choose to avoid that, as follows:
...
;
...
filter
...
:
...
(X
...
-
...
>boolean) X -> X ; 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 (restl))) else(filter-helper (restl)))]))] (filter-helper l)))
HTML |
---|
HTML |
---|
filterexercises
HTML |
---|
HTML |
---|
HTML |
---|
HTML |
---|
HTML |
---|
UsingDrScheme
HTML |
---|
<TABLE BORDER=1 BGCOLOR=#EFEFDF class="MsoBodyTextIndent"> |
HTML |
---|
<CAPTION class="MsoBodyTextIndent"> |
filter
exercises
HTML |
---|
</CAPTION> |
HTML |
---|
<tr> |
HTML |
---|
<td> |
HTML |
---|
<ol> |
HTML |
---|
<li> |
Using DrScheme's "Check Syntax" feature to identify
where each variable is bound in the second definition.
Recall that when you put your cursor above a binding instance,
it will draw arrows to the uses, and when you put your
cursor above a use, it will draw an arrow to its binding instance.
HTML |
---|
</li> |
HTML |
---|
<li> |
Using either definition of
...
filter
, define a
function that takes a list of numbers and returns a list of
all the positive numbers in that list.
HTML |
---|
</li> |
...
HTML |
---|
</td> |
HTML |
HTML |
---|
HTML |
---|
HTML |
---|
HTML |
---|
HTML |
---|
Anchor | ||||
---|---|---|---|---|
|
...
mapReview
HTML |
---|
</A> |
We are familiar with writing functions such as the following:
...
...
;
...
double-nums
...
:
...
...
-> number ; Given a list of numbers,returna 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 (resta-lon))))) ; lessthan3-nums : number -> boolean ; Given a list of numbers,returna 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 (resta-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
...
:
...
(X
...
-
...
> Y)
...
...
-> Y (define
...
(map
...
f l) (cond (empty?
...
...
...
...
...
...
...
...
...
...
...
...
...
))
...
;
...
double-num
...
:
...
number
...
->
...
number
...
(define
...
(double-num
...
n)
...
(*
...
2
...
n))
...
;
...
double-nums
...
:
...
...
->
...
...
(define
...
(double-nums
...
a-lon)
...
(
...
mapdouble-num
...
a-lon))
...
;
...
lessthan-3-nums
...
:
...
...
->
...
...
(define
...
(lessthan3-nums
...
a-lon)
...
(map
...
(lambda
...
(
...
< n 3)) a-lon))
...
map
abstracts mapabstracts 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 understandmapis by the following equation.
It describes what map
does describeswhatmapdoes without the usually
extraneous details of how it ofhowit does it.
...
...
(map
...
f
...
(list
...
x<sub>1</sub>
...
… x<sub>n</sub>))
...
=
...
(list
...
(f
...
x<sub>1</sub>)
...
… (f
...
x<sub>n</sub>))
...
HTML |
---|
<TABLE BORDER=1 BGCOLOR=#EFEFDF class="MsoBodyTextIndent"> |
HTML |
---|
<CAPTION class="MsoBodyTextIndent"> |
HTML |
---|
mapexercises map
exercises
HTML |
---|
</CAPTION> |
HTML |
---|
<TR> |
HTML |
---|
HTML |
---|
HTML |
---|
<LI> |
Writedouble-numsusingmapand Write double-nums
using map
and
local, without a global functionaglobalfunction
double-num.
HTML |
---|
HTML |
---|
<LI> |
Writedouble-numsusingmapand Write double-nums
using map
and
lambda, without any named function like
double-num.
HTML |
---|
HTML |
---|
HTML |
---|
HTML |
---|
</TR> |
HTML |
---|
HTML |
---|
<A NAME="summary"> |
Anchor | ||||
---|---|---|---|---|
|
HTML |
---|
Abstract functions are 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 clearer and more
understandable.
The examples in this lab are certainly not the only abstract functions,
but they are among those that are particularly useful because they
correspond to common list computations.
Because Scheme has lists built in and since these functions are so useful,
Scheme has them pre-defined.
HTML |
---|
Usually, using abstract functions takes the place of following our
standard templates. So, what happens to our design recipes?
HTML |
---|
</STRONG> |
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
amongfindfilterandmapamong
the easier ones to use at first.
On the other hand, foldr
and foldl
are foldrandfoldlare more general
and take more practice to get comfortable with.
You will get practice on homeworks and the next two exams.
HTML |
---|
<A NAME="foldr"> |
Anchor | ||||
---|---|---|---|---|
|
HTML |
---|
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 valuebaseas the result for the empty list
and a function f
to functionfto 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
...
x<sub>1</sub>
...
x<sub>2</sub>
...
… x<sub>n</sub>))
...
=
...
(f
...
x<sub>1</sub>
...
(f
...
x<sub>2</sub>
...
… (f
...
x<sub>n</sub>
...
base)))
...
Many functions we've written fit this pattern, although
this might not be obvious at first.
This function was discussed in class, but with the name
...
fun-for-l
and its arguments in a different order.
There we saw this is also equivalent to turning
our list template into an abstract function.
HTML |
---|
<TABLE BORDER=1 BGCOLOR=#EFEFDF class="MsoBodyTextIndent"> |
HTML |
---|
<CAPTION class="MsoBodyTextIndent"> |
foldr
exercises
HTML |
---|
</CAPTION> |
HTML |
---|
<TR> |
HTML |
---|
<TD> |
HTML |
---|
<OL> |
HTML |
---|
<LI> |
HTML |
---|
foldrexercises
HTML |
---|
HTML |
---|
HTML |
---|
HTML |
---|
HTML |
---|
Based upon this equation, what should the following evaluate to?
Think about them first, then try them in DrSchemeinDrScheme
(where
...
foldr
is pre-defined).
...
...
(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)))
...
HTML |
---|
</li> |
HTML |
---|
What is the contract for foldr
forfoldr?
You should be able to determine this from the equation and
examples above.
First ask yourself the question assuming the input list
is a list of numbers, then generalize.
HTML |
---|
</li> |
HTML |
---|
<LI> |
Using foldr
Usingfoldr, define a function to compute
the product of a list of numbers.
HTML |
---|
</li> |
HTML |
---|
<LI> |
Using foldr
, define map
Usingfoldr, definemap.
HTML |
---|
HTML |
---|
Define the function myfunctionmy-foldr to foldrto 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 foldrto make sure they give the same results for
the same inputs.
HTML |
---|
HTML |
---|
HTML |
---|
...
If you have time…time...
HTML |
---|
</strong> |
Using foldr
Usingfoldr, define a function to compute
whether all elements in a list of numbers are greater than 6.
Then generalize this to using
...
usingfoldr
to define
...
filter
.
HTML |
---|
HTML |
---|
</OL> |
HTML |
---|
HTML |
---|
</TR> |
HTML |
---|
</TABLE> |
Anchor | ||||
---|---|---|---|---|
|
Here's a few more pre-defined abstract functions:
...
...
(andmap
...
f
...
(list
...
x<sub>1</sub>
...
… x<sub>n</sub>))
...
=
...
(and
...
(f
...
x<sub>1</sub>)
...
… (f
...
x<sub>n</sub>))
...
(ormap
...
f
...
(list
...
x<sub>1</sub>
...
… x<sub>n</sub>))
...
=
...
(or
...
(f
...
x<sub>1</sub>)
...
… (f
...
x<sub>n</sub>))
...
(build-list
...
n
...
f)
...
=
...
(list
...
(f
...
0)
...
… (f
...
(sub1
...
n)))
...
The following is a quick summary of the abstract functions mentioned
in this lab:
HTML |
---|
<ul class="MsoBodyTextIndent"> |
HTML |
---|
filter Code Block
-- –
selects some elements from a list
HTML |
---|
</li> |
HTML |
---|
<li> |
map Code Block
– -
applies a function to each list element
HTML |
---|
</li> |
HTML |
---|
<li> |
...
andmap
/
...
ormap
-- –
applies a function to each list element and combines the resulting booleans
...
booleans
HTML |
---|
<li> |
...
HTML |
---|
build-list
– -
constructs a list of the given length according to the given function
HTML |
---|
</li> |
HTML |
---|
<li> |
...
foldr
/
...
foldl
– -
combines all elements of a list
HTML |
---|
HTML |
---|
HTML |
---|
<TABLE BORDER=1 BGCOLOR=#EFEFDF class="MsoBodyTextIndent"> |
HTML |
---|
Exercises
HTML |
---|
</CAPTION> |
HTML |
---|
HTML |
---|
<td> |
The following can be defined using some combination of
the pre-defined abstract functions.
HTML |
---|
<ol> |
HTML |
---|
<li> |
Define a function that, given a list of numbers, returns
the sum of all the positive numbers in the list.
HTML |
---|
</li> |
HTML |
---|
Define a function that, given a list of anything, determines
whether all of the numbers in the list are even.
HTML |
---|
</li> |
HTML |
---|
HTML |
---|
...
If you have time…time...
HTML |
---|
HTML |
(This is from the last lab, but use abstract functions this time,
and then compare the function to the one you wrote last week.)
Develop a function that, given
HTML |
---|
n
HTML |
---|
and
HTML |
---|
i
HTML |
---|
</VAR> |
normally
returns the list of length
HTML |
---|
i
HTML |
---|
</VAR> |
of numbers
up to
HTML |
---|
<VAR> |
n
HTML |
---|
:
...
...
(list
...
<VAR>n</VAR>-(<VAR>i</VAR>-1)
...
… <VAR>n</VAR>-1
...
<VAR>n</VAR>)
...
More concretely, e.g.,
...
...
(nums-upto-help
...
5
...
0)
...
⇒ empty (nums-upto-help 5 2) ⇒ (list 4 5) (nums-upto-help
...
5
...
5)
...
⇒ (list
...
1
...
2
...
3
...
4
...
5)
...
(nums-upto-help
...
6
...
5)
...
⇒ (list
...
2
...
3
...
4
...
5
...
6)
...
(nums-upto-help
...
7
...
5)
...
⇒ (list
...
3
...
4
...
5
...
6
...
7)
...
For simplicity, you may assume that
HTML |
---|
<VAR> |
i
HTML |
---|
≤
HTML |
---|
n
HTML |
---|
.
This should just follow the template for
natural numbers on
HTML |
---|
i
HTML |
---|
.
HTML |
---|
</li> |
HTML |
---|
<LI> |
HTML |
---|
<strong>
HTML |
---|
</strong> |
Define andmap
Defineandmap, which computes
whether all elements in a list of booleans are true:
...
...
(andmap
...
f
...
(list
...
x<sub>1</sub>
...
… x<sub>n</sub>))
...
=
...
(and
...
(f
...
x<sub>1</sub>)
...
… (f x<sub>n</sub>))First, define it recursively following the list template, then
define it using
...
foldr
and
...
andmap
...
map
,
then using only
...
onlyfoldr
.
HTML |
---|
HTML |
---|
HTML |
---|
</td> |
HTML |
---|
HTML |
---|
</table> |
HTML |
---|
<A NAME="foldl"> |
Anchor | ||||
---|---|---|---|---|
|
HTML |
---|
The mathematically inclined might have noticed that foldr
thatfoldr
groups the binary operations right-associatively. Thus the "r" in the name.
What if we want to group left-associatively?
Well, we also have the following:
...
...
(foldl
...
f
...
base
...
(list
...
x<sub>1</sub>
...
x<sub>2</sub>
...
… x<sub>n</sub>))
...
=
...
(f
...
x<sub>n</sub>
...
… (f
...
x<sub>2</sub>
...
(f
...
x<sub>1</sub>
...
base))
...
…)
...
HTML |
---|
HTML |
---|
<CAPTION class="MsoBodyTextIndent"> |
foldl
exercises
foldlexercises
HTML |
---|
HTML |
HTML |
---|
<TR> |
HTML |
---|
<TD> |
HTML |
---|
<OL> |
HTML |
---|
Based upon this equation, what should the following evaluate to?
Think about them, then try them in DrSchemeinDrScheme
(where
...
foldl
is pre-defined).
...
...
(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)))
...
Compare the results to those for
...
foldr
.
HTML |
---|
HTML |
---|
Do
...
(foldr
...
+
...
0
...
<em>numlist</em>)
...
and
...
(foldl
...
+
...
0
...
<em>numlist</em>)
...
always give the same results?
Hint: Think back a couple labs.
HTML |
---|
</li> |
HTML |
---|
<LI> |
Define the function
...
my-foldl
to satisfy the above
equation, testing it against Scheme's built-in
...
foldl
.
Hint: Use
...
Usereverse
.
HTML |
---|
HTML |
---|
<li> |
HTML |
---|
If you've read ahead a few chapters:
HTML |
---|
</strong> |
Define my-foldl
without using
...
Definemy-foldlwithout using
reverse
.
Hint: Use an accumulator.
...
HTML |
---|
HTML |
---|
</TD> |
HTML |
---|
HTML |
---|
HTML |
---|
Anchor | ||||
---|---|---|---|---|
|
Abstract functions are also quite useful. Scheme has lists and
their abstract functions built-in, so they get more attention,
but the ideas transfer to trees perfectly well.
For example, one definition of binary tree is the following:
...
...
(define-struct
...
node
...
(n
...
left
...
right))
...
;
...
A
...
binary
...
tree
...
of
...
numbers
...
(btn)
...
is
...
;
...
-
...
empty
...
;
...
-
...
(make-node
...
n
...
l
...
r)
...
;
...
where
...
n
...
is
...
a
...
number
...
and
...
l,r are btns
HTML |
---|
HTML |
---|
HTML |
---|
<TABLE BORDER=1 BGCOLOR=#EFEFDF class="MsoBodyTextIndent"> |
HTML |
---|
Tree exercises
HTML |
---|
</CAPTION> |
HTML |
---|
HTML |
---|
HTML |
---|
...
If you have time…time...
HTML |
---|
</strong> |
HTML |
---|
HTML |
---|
<li> |
Define a
...
map
-like function on btns.
HTML |
---|
</li> |
HTML |
---|
HTML |
---|
...
Semi-challenge:
HTML |
---|
Define a afoldr
Code Block |
---|
foldr |
-like function on btns.
Hint: Whereas Whereasfoldr
Code Block |
---|
foldr |
on lists took a binary
function argument, this one needs a ternary function argument.
HTML |
---|
</li> |
HTML |
---|
HTML |
---|
</td> |
HTML |
---|
HTML |
---|
</table> |
HTML |
---|
!! Access Permissions
- Set ALLOWTOPICCHANGE = Main.TeachersComp211Group