...
Natural
...
Numbers
...
&
...
List
...
Abbreviations
...
Instructions
...
for
...
students
...
&
...
labbies:
...
Students
...
use
...
DrScheme,
...
following
...
the
...
design
...
recipe,
...
working
...
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.
...
Students
...
should
...
feel
...
free
...
to
...
skip
...
the
...
challenge
...
exercises.
...
Scheme's Built-in
...
Naturals
...
We
...
already
...
know
...
Scheme
...
has
...
lots
...
of
...
numbers
...
built-in,
...
like
...
3,
...
17.83,
...
and
...
-14/3.
...
It
...
is
...
often
...
convenient
...
to
...
limit
...
our
...
attention
...
to
...
a
...
subset
...
of
...
these
...
such
...
as
...
the
...
naturals:
...
0,
...
1,
...
2,
...
3,
...
...
...
.
...
We
...
can
...
define
...
the
...
naturals
...
and
...
its
...
template
...
as
...
follows:
| Code Block |
|---|
} ; A natural (*N*) is either: ; - 0 ; - (add1 n) ; where n is a natural ; Template ; nat-f : natural -> ... (define (f ... n ... ) (cond [(zero? n) ...] [(positive? n) ... (f ... (sub1 n) ... ) ...])) {code} |
Of
...
course,
...
we
...
already
...
know
...
what
...
the
...
example
...
data
...
looks
...
like:
...
0,
...
1,
...
2,
...
3,
...
...
...
Unlike
...
most
...
data
...
definitions,
...
we
...
are
...
not
...
defining
...
new
...
Scheme
...
values
...
here
...
(
...
i.e.
...
,
...
there's
...
no
...
define-struct
...
),
...
but
...
we
...
are
...
defining
...
(identifying)
...
a
...
subset
...
of
...
Scheme
...
numbers.
...
The
...
definition
...
and
...
template
...
use
...
some
...
built-in
...
Scheme
...
functions
...
(
...
add1
...
, sub1, zero?
...
)
...
that
...
may
...
be
...
unfamiliar,
...
but
...
which
...
mean
...
just
...
what
...
their
...
names
...
suggest.
...
If
...
we
...
ignore
...
that
...
Scheme
...
has
...
a
...
built-in
...
function
...
{+},
...
we
...
could
...
define
...
it
...
ourselves
...
as
...
follows:
| Code Block |
|---|
} ; add: natural natural \-> natural ; Purpose: (add x y) returns the sum of x and y . (define (add n m) (cond [(zero? n) m] [(positive? n) (add1 (add (sub1 n) m))])) {code} *Optional Exercise* * Use the stepper on {{(add 2 2)}} to see how it works. Example functions h3. Exercises Write each of the functions on *N*. # The factorial function {{!}}, which is defined by the equations: {{(! 0) = 1}} , and {{(! (add1 n)) = (* (add1 n) (! n))}}. # The function {{down}} that takes an input {{n}} in *N* and returns the list of *N* {{(n ... 1 0)}}. # The function {{up}} that takes an input {{n}} in *N* and returns the list of *N* {{(0 1 ... n)}}. Hint: define an auxiliary function {{upfrom: N N -> list of N}} such that {{(upfrom m n)}} returns {{(m (add1 m) ... n)}}. Assume that {{m}} is less than or equal to {{n}}. h2. List Abbreviations Chapter 13 of the book introduces some new, compact methods for representing lists, which have already been mentioned in lecture. The following exercises simply let you explore how this notation behaves. h3. Finger Exercises on list abbreviations # Evaluate he following in the DrScheme interactions pane. You can cut and paste to save time if you want. {code} |
Optional Exercise
- Use the stepper on
(add 2 2)to see how it works.
Example functions
Exercises
Write each of the functions on N.
- The factorial function
!, which is defined by the equations:
(! 0) = 1 , and
(! (add1 n)) = (* (add1 n) (! n)).
- The function
downthat takes an inputnin N and returns the list of N
(n ... 1 0).
- The function
upthat takes an inputnin N and returns the list of N
(0 1 ... n). Hint: define an auxiliary functionupfrom: N N -> list of Nsuch that
(upfrom m n)returns(m (add1 m) ... n). Assume thatmis less than or equal ton.
List Abbreviations
Chapter 13 of the book introduces some new, compact methods for representing lists, which have already been mentioned in lecture. The following exercises simply let you explore how this notation behaves.
Finger Exercises on list abbreviations
- Evaluate he following in the DrScheme interactions pane. You can cut and paste to save time if you want.
Code Block (list 1 2 3) (cons 1 (cons 2 (cons 3 empty))) (list 1 2 3 empty) (cons 1 (cons 2 (cons 3 (cons empty empty)))
...
- Rewrite the following using
list.Code Block (cons (cons 1 empty) empty) (cons 1 (cons (cons 2 (cons 3 empty)) (cons 4 (cons (cons 5 empty) empty)))) (cons (cons (cons 'bozo empty) empty) empty)
List constants
Using ' notation we can abbreviate constant lists even more.
Finger Exercises on list constants
- Evaluate he following in the DrScheme interactions pane. You can cut and paste to save time if you want. Note that
'produces strange results for embedded references totrue,false,(), andempty.
| Code Block |
|---|
{code} h2. List constants Using {{'}} notation we can abbreviate _constant_ lists even more. h3. Finger Exercises on list constants # Evaluate he following in the DrScheme interactions pane. You can cut and paste to save time if you want. Note that {{'}} produces strange results for embedded references to {{true}}, {{false}}, {{()}}, and {{empty}}. {code} '(1 2 3 4) (list 1 2 3 4) '(rabbit bunny) (list 'rabbit 'bunny) '(rabbit (2) (3 4 5)) (list 'rabbit (list 2) (list 3 4 5)) '(true) '(empty) '(()) (list empty) (list ()) (list 'empty) (list '()) {code} |
'(1
...
2
...
3
...
4)
...
=>
...
(list
...
1
...
2
...
3
...
4)
...
=>
...
(cons
...
1
...
(cons
...
2
...
(cons
...
3
...
(cons
...
4
...
empty))))
...
'(rabbit
...
bunny)
...
=>
...
(list
...
'rabbit
...
'bunny)
...
=>
...
(cons
...
'rabbit
...
(cons
...
'bunny
...
empty))
...
'(rabbit
...
(2)
...
(3
...
4
...
5))
...
=>
...
(list
...
'rabbit
...
(list
...
2)
...
(list
...
3
...
4
...
5))
...
(cons
...
'rabbit
...
(cons
...
(cons
...
2
...
empty)
...
(cons
...
(cons
...
3
...
(cons
...
4
...
(cons
...
5
...
empty)))
...
empty)))
| HTML |
|---|
| HTML |
|---|
Exercise
| HTML |
|---|
| HTML |
|---|
| HTML |
|---|
Re-write the lists from above using
'
notation.
| HTML |
|---|
| HTML |
|---|
| HTML |
|---|
We can think of the
'
as distributing over the elements. We apply this rule recursively (Yes! Recursion strikes again!) until there are no more'(
s left.
'(rabbit (2) (3 4 5)) => (list 'rabbit '(2) '(3 4 5)) (list 'rabbit (list '2) (list '3 '4 '5)) => ... => (cons 'rabbit (cons (cons 2 empty) (cons (cons 3 (cons 4 (cons 5 empty))) empty)))
| HTML |
|---|
NB:
| HTML |
|---|
'1
reduces to1
. In general,'<a number>
evaluates to<a number>
.
| HTML |
|---|
| HTML |
|---|
Exercise
| HTML |
|---|
| HTML |
|---|
| HTML |
|---|
What do we get in these cases?
'((make-posn 1 2)) '(1 (+ 1 1) (+ 1 1 1))
| HTML |
|---|
| HTML |
|---|
| HTML |
|---|
You cannot use list abbreviation one nested in another. For example
'(1 '(+ 1 1)) (will be treated in DrScheme as
(list 1 (list 'quote (list '+ 1 1)))
If we want to apply functions, we have to use eitherconsorlist. (Not exactly true. There is another abbreviation,quasiquote, that we won't talk about in this course.)
| HTML |
|---|
| HTML |
|---|
Trees & Mutually Recursive Data Definitions
| HTML |
|---|
| HTML |
|---|
| HTML |
|---|
| HTML |
|---|
Instructions for students & labbies:
| HTML |
|---|
| HTML |
|---|
Students use DrScheme, following the design recipe,
working 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.
Students should feel free to skip the challenge exercises.
Trees
In class, we used ancestor family trees as an example form of trees.
In ancestor family trees, each person (a
make-child
structure)
has 0, 1, or 2 ancestors (alsomake-child
structures).
Here, we'll use a similar, but slightly different, form of trees for
more experience.
In mathematics, we can model arithmetic expressions as trees. For
example,
5+(1-8)×(7+1)
...
or
...
equivalently,
...
the
...
Scheme
...
code
...
(
...
+
...
5
...
(
...
*
...
(
...
-
...
1
...
8)
...
(
...
+
...
7
...
1)))
...
is
...
pictorially
+ / \ 5 × / \ - + / \ / \ 1 8 7 1
This tree form has some advantages. To understand the more familiar
linear form, you must know about the order of operator precedence,
whereas that is unnecessary in the tree form. The tree also eliminates
the need for parentheses. The tree also gets us away from the relatively
minor concerns of the precise details of mathematical or Scheme
notation, like infix vs. prefix operators.
Consider if you were developing a computer program like DrScheme
(or, similarly, a "compiler," if you know what that is).
Such a program would take the linear form, which is convenient for
a person to type in, but then convert or
| HTML |
|---|
parse
| HTML |
|---|
it to the tree form
for internal use.
Since parsing is beyond the scope of this course, let's just skip straight
to the tree form.
We'll require that each addition, subtraction, multiplication, and
division has exactly two subexpressions. Of course, recursively,
each subexpression can be another addition, subtraction, multiplication,
or division. As a base case, an expression can also be a number.
(define-struct add (m n)) (define-struct sub (m n)) (define-struct mul (m n)) (define-struct div (m n)) ; An Arithmetic-Expression (AExp) is one of ; - a number ; - (make-add <var>m</var> <var>n</var>) ; where <var>m</var>,<var>n</var> are AExps ; - (make-sub <var>m</var> <var>n</var>) ; where <var>m</var>,<var>n</var> are AExps ; - (make-mul <var>m</var> <var>n</var>) ; where <var>m</var>,<var>n</var> are AExps ; - (make-div <var>m</var> <var>n</var>) ; where <var>m</var>,<var>n</var> are AExps
With this data definition, the above tree is modeled by the structure
(define AExp1 (make-add 5 (make-mul (make-sub 1 8) (make-add 7 1))))
Another sample AExp is
(define AExp2 16)
As always, we distinguish between the information (the mathematical
expression or its corresponding tree) and its data representation
(this AExp).
Just writing this piece of data doesn't mean we can do anything with it
yet, such as compute the intended result.
| HTML |
|---|
| HTML |
|---|
Exercise
| HTML |
|---|
| HTML |
|---|
| HTML |
|---|
| HTML |
|---|
| HTML |
|---|
Make more example data.
| HTML |
|---|
| HTML |
|---|
Develop the function
evaluate
which takes an
AExp as input and returns the number that the expression
mathematically computes. For example,
(evaluate AExp1)
should result in -51, and
(evaluate AExp2)
should result in 16.
| HTML |
|---|
| HTML |
|---|
| HTML |
|---|
Challenge exercise:
| HTML |
|---|
Let's say we hadmanybasic operations, not just
these four. We would want to have one structure for any
binary operation, using a separate data definition enumerating
all of our operations. Rewrite the data definitions, examples,
andevaluate
for this.
As a further challenge, also allow unary operations.
| HTML |
|---|
| HTML |
|---|
| HTML |
|---|
| HTML |
|---|
| HTML |
|---|
Files and Directories
The following are data definitions for one possible (simplified) representation
of files and directories (a.k.a. folders). These definitions follow the Windows convention of attaching a name to a file. They also collapse the definition of the directory type into a clause of the definition of for file, which makes the definitions more compact but makes it less clear how to write functions that process directories (instead of files). For this reason, none of the following exercises uses a directory as the primary input to a function.
Observe the mutual recursion between files and list-of-files.
| HTML |
|---|
(define-struct dir (name contents))
; A file is one of
; - a symbol
; representing a "simple" file's name
; - a directory
; (make-dir name contents)
; where name is a symbol, and contents is a l-o-f.
; A list-of-files (l-o-f) is one of
; - empty
; - (cons f lofd)
; where f is a file, and lofd is a l-o-f
| HTML |
|---|
This is very similar to the descendant trees data structure seen in class.
| HTML |
|---|
Tree-based data structures are very common!
| HTML |
|---|
| HTML |
|---|
| HTML |
|---|
Directory exercises
| HTML |
|---|
| HTML |
|---|
| HTML |
|---|
| HTML |
|---|
| HTML |
|---|
Create some sample data for the above types.
| HTML |
|---|
| HTML |
|---|
Write the templates for the above types.
| HTML |
|---|
| HTML |
|---|
Develop a function
| HTML |
|---|
; find? : symbol file -> boolean
; Returns whether the filename is anywhere in the
; tree of files represented by the file. This includes both
; simple file names and directory names.
| HTML |
|---|
| HTML |
|---|
| HTML |
|---|
Aside
| HTML |
|---|
| HTML |
|---|
| HTML |
|---|
Note that this is a vast simplification of
find
, the
mother-of-all everything-but-the-kitchen-sink
...
UNIX
...
directory
...
traversing
...
command.
...
If
...
you're
...
curious,
...
logon
...
to
...
a
...
UNIX
...
machine
...
at
...
a
...
UNIX
...
shell
...
prompt,
...
enter
...
man
...
findto
...
see
...
what
...
it
...
can
...
do.
| HTML |
|---|
| HTML |
|---|
| HTML |
|---|
| HTML |
|---|
| HTML |
|---|
Use DrScheme's
...
stepper
...
to
...
step
...
through
...
an
...
example
...
use
...
offind?.
...
Following
...
the
...
templates
...
leads
...
to
...
an
...
overall
...
strategy
...
known
...
as
...
| HTML |
|---|
depth-first
...
search
...
| HTML |
|---|
. I.e.,
...
it
...
explores
...
each
...
tree
...
branch
...
to
...
the
...
end
...
before
...
moving
...
on
...
to
...
the
...
next
...
branch.
| HTML |
|---|
| HTML |
|---|
Develop the following function:
| HTML |
|---|
; any-duplicate-names?
...
:
...
file
...
->
...
boolean
...
;
...
Returns
...
whether
...
any
...
(sub)directory
...
directly
...
or
...
indirectly
...
contains
...
;
...
another
...
directory
...
or
...
file
...
of
...
the
...
same
...
name.
...
It
...
does
...
NOT
...
check
...
;
...
for
...
duplicated
...
names
...
in
...
separate
...
branches
...
of
...
the
...
tree.
...
| HTML |
|---|
There's
...
a
...
straightforward
...
way
...
that
...
just
...
follows
...
the
...
template.
| HTML |
|---|
| HTML |
|---|
| HTML |
|---|
Challenge:
| HTML |
|---|
Develop a program to check for duplicated names among
alldirectories and files in the given tree, not just
subdirectories.
Here's a hint.
| HTML |
|---|
| HTML |
|---|
Develop the following function:
| HTML |
|---|
; flatten-dir-once
...
:
...
symbol
...
file
...
->
...
(file
...
or
...
l-o-f)
...
;
...
Returns
...
a
...
structure
...
like
...
the
...
original
...
file,
...
except
...
that
...
any
...
;
...
(sub)directory
...
with
...
that
...
name
...
is
...
removed
...
and
...
its
...
contents
...
;
...
moved
...
up
...
one
...
level.
...
| HTML |
|---|
Here are two pictorial examples, in both cases removing the directory
namedto-remove.
...
These
...
illustrate
...
why
...
this
...
function
...
can
...
return
...
either
...
a
...
file
...
or
...
a
...
list
...
of
...
files.
...
| HTML |
|---|
| HTML |
|---|
| HTML |
|---|
| HTML |
|---|
| HTML |
|---|
Input
| HTML |
|---|
| HTML |
|---|
Output
| HTML |
|---|
| HTML |
|---|
| HTML |
|---|
| HTML |
|---|
Example 1:
| HTML |
|---|
| HTML |
|---|
| HTML |
|---|
foo
/ | \
bar baz to-remove
/ \
one two
| HTML |
|---|
| HTML |
|---|
| HTML |
|---|
| HTML |
|---|
foo
/ / \ \
bar baz one two
| HTML |
|---|
| HTML |
|---|
| HTML |
|---|
| HTML |
|---|
| HTML |
|---|
Example 2:
| HTML |
|---|
| HTML |
|---|
| HTML |
|---|
to-remove
/ | \
foo bar baz
| HTML |
|---|
| HTML |
|---|
| HTML |
|---|
| HTML |
|---|
foo bar baz
| HTML |
|---|
| HTML |
|---|
| HTML |
|---|
| HTML |
|---|
| HTML |
|---|
Follow the templates and think about a single
case at a time.
| HTML |
|---|
If you do that, it shouldn't be too difficult. If you don't, you'll
probably have real trouble.
| HTML |
|---|
| HTML |
|---|
| HTML |
|---|
| HTML |
|---|
| HTML |
|---|
| HTML |
|---|
| HTML |
|---|
Sample solutions.
| HTML |
|---|
| HTML |
|---|
| HTML |
|---|
| HTML |
|---|
| HTML |
|---|
!! Access Permissions
- Set ALLOWTOPICCHANGE = Main.TeachersComp211Group