Versions Compared

Old Version 1

changes.mady.by.user Michael Lightfoot

Saved on

compared with

New Version 2

changes.mady.by.user Sbirlea, Alina

Saved on

Key

  • This line was added.
  • This line was removed.
  • Formatting was changed.
HTML
<div id="header">

Natural Numbers & List Abbreviations

HTML
</div>
HTML
<div id="content">
HTML
<strong>

...

Instructions for students & labbies:

HTML
</font>
HTML
</strong>

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.

Natural Numbers

Review: Definition

In class, we defined our own version of natural numbers, its
corresponding template, and example data:

...

...

;

...

A

...

Natural

...

is

...

one

...

of
; - 'Zero
; - (make-next

...

n)
; where n is a Natural
(define-struct

...

next

...

(nat))

...


; f : Natural -> …

(define (f n)
(cond (symbol? n) &hellip; (next? n) &hellip;(f

...

(next-nat

...

n))&hellip;

...

))

...

(define

...

Zero

...

'Zero)

...


(define

...

One

...

(make-next

...

Zero))

...


(define

...

Two

...

(make-next

...

One))

...


(define

...

Three

...

(make-next

...

Two))

...


(define

...

Four

...

(make-next

...

Three))

...

Here is an example function:

...

; add-Nat : Natural Natural -> Natural
; Returns the result of adding two Naturals.
(define (add-Nat

...

n

...

m)

...

(cond

...

(symbol?

...

n)

...

m

...

(next?

...

n)

...

(make-next

...

(add-Nat

...

(next-nat

...

n)

...

m))

...

))

...

HTML
<CAPTION class="MsoBodyTextIndent">

Exercises

HTML
</CAPTION>
HTML
<tr>
HTML
<td>
HTML
<ol>

Use the stepper on

Code Block
(add-Nat Two Two)

Exercises

  • Use the stepper on (add-Nat Two Two)to see how it works.

...

HTML
</ol>
HTML
</td>

...

...

</tr>
HTML
</table>

We do not suggest actually using this data definition in everyday programs.
There are two reasons for looking at this definition.
First, it is a second example (after lists), of recursively defined
data structures and how we write functions on them.
Second, we can take this idea and apply it to Scheme's built-in numbers.
The lab's examples will explore both of these.

...

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,
the naturals: 0, 1, 2, 3, …....
We can define the naturals and its template as follows:

...

; A natural is one of
; - 0
; - (add1 n)
; where n is a natural
; f : natural -> …
(define (f n) (cond (zero? n) &hellip; (positive? n) &hellip;(f (sub1 n))&hellip;

...

))

...

Of course, we already know what the example data looks like:
0, 1, 2, 3, …...

Unlike for Naturals, we are not defining new Scheme values here
(i.e., there's no

...

define-struct

...

), but we are defining
a subset of all Scheme numbers that we are interested in.
The definition and template use some built-in Scheme functions that
we haven't seen before (

...

add1

...

,

...

sub1

...

,

...

zero?

...

), but which mean just what their names imply.

If we choose to ignore that Scheme has a built-in function

...

+

...

,
we could define it ourselves, just like the above

...

add-Nat
on
Naturals:

...

;

...

add-nat

...

:

...

natural

...

natural

...

-

...

> natural
; Returns the result of adding two naturals.

(define (add-nat

...

n

...

m)

...

(cond

...

(zero?

...

n)

...

m

...

(positive?

...

n)

...

(add1

...

(add-nat

...

(sub1

...

n)

...

m))

...

))

Exercise

HTML
<TABLE BORDER=1 BGCOLOR=#EFEFDF class="MsoBodyTextIndent">

HTML
<CAPTION class="MsoBodyTextIndent">

Exercise

HTML
</CAPTION>
HTML
<tr>
HTML
<td>
  • Use the stepper on

...

  • (add-nat

...

  • 2

...

  • 2)

...

  • to see how it works.
HTML
</td>
HTML
</tr>
HTML
</table>

Example functions

HTML
<TABLE BORDER=1 BGCOLOR=#EFEFDF class="MsoBodyTextIndent">

HTML
<CAPTION class="MsoBodyTextIndent">

Exercises

HTML
</CAPTION>
HTML
<tr>
HTML
<td>

Example functions

Exercises

Write each of the functions Write each of the functions on both Naturals and naturals.
Once you have successfully written one version, the other
should be a matter of copy-and-paste-and-edit.
Each is described using the naturals, for convenience, with

HTML
<var>

n

HTML
</var>

as the input.

HTML
<ol>
HTML
<li>

n as the input.

#Factorial Factorial, which is defined as

0! = 1, and
(

<var>
HTML
n
 HTML
</var>
+1)! = (
<var>
 HTML
n
</var>
 HTML
+1) × (
 HTML
<var>
n
 HTML
</var>
!).
</li>
 HTML
 HTML
<li>
A function returning the list of naturals (or Naturals)
 HTML
<var>
n
 HTML
</var>
…0 ...0 in left-to-right order.
 HTML
<li>
</li>
 HTML
Given a base
<var>
 HTML
b
</var>
 HTML
,
,
 the integral part of the logarithm
 _ log
 HTML
<var>
<sub>
 HTML
b
 HTML
</var>
 HTML
</sub>
 HTML
<var>
n
 HTML
</var>
_,
 Compute this by recursively counting the number of times
 you can divide the number by the base.
<strong>
 HTML
Note:
 HTML
</strong>
Like the in-class example 
...
examplegeq
 ,
 this doesn't follow the natural's data-defined template.
 HTML
</li>
 HTML
<li>
 HTML
...
Challenge exercise, this is much tougher at this
 point in the course
 HTML
</strong>
:
 A function returning the list of naturals (or Naturals)
 0… 0...
 HTML
<var>
n
 HTML
</var>
in left-to-right order.
 HTML
</li>
 HTML
 HTML
</ol>
 HTML
 HTML
</td>
 HTML
</tr>
 HTML
</table>
...
Built-in Natural Numbers and Templates
At the beginning of the course, we wrote lots of functions on numbers
 without using templates, and just using mathematical formulae.
 In those cases, we were writing functions on numbers
 without viewing the number as having any kind of internal structure.
Here, we are considering functions that work only workonly on naturals.
 By adopting the recursive definition on naturals, we get a benefit –-
 the natural's template guides us in writing our functions.
However, as examples like the logarithm above show, not all functions
 will follow the template that mimics the data definition.
 This is a leading example, as we will soon be
 introducing a more flexible template to help in such situations.
List Abbreviations
Chapter 13 of 13of the book introduces some new, compact methods for representing lists.
<strong>
 HTML
NB:
 HTML
</strong>
From now on, we need to use the "Beginning Student with List Abbreviations" language. Change this now. (The chapter in the book lists "Intermediate Student". We'll get to "Intermediate Student" a little later.)
...
list
Using
...

 list
 we can quickly write a list with many fewer
...
()
 s:
...
(list 
...
 1 
...
 2 
...
 3) 
...
 => 
...
 (cons 
...
 1 
...
 (cons 
...
 2 
...
 (cons 
...
 3 
...
 empty)))
...
Notice that we did not end the
...

 list
 construct with an 
 Code Block
empty
. anempty
 . What would happen if we did?:
...
(list 
...
 1 
...
 2 
...
 3 
...
 empty) 
...
 => 
...
 (cons 
...
 1 
...
 (cons 
...
 2 
...
 (cons 
...
 3 
...
 (cons 
...
 empty 
...
 empty))))
...
The last element has become a list of lists.
<TABLE BORDER=1 BGCOLOR=#EFEFDF class="MsoBodyTextIndent">
 HTML
 HTML
<CAPTION class="MsoBodyTextIndent">
Exercise
 HTML
<tr>
</CAPTION>
 HTML
<td>
 HTML
Play with
...
 list
...
list
 a bit. Can you write these?
...
(cons 
...
 (cons 
...
 1 
...
 empty) 
...
 empty) 
...
 (cons 
...
 1 
...
 (cons 
...
 (cons 
...
 2 
...
 (cons 
...
 3 
...
 empty)) 
...
 (cons 
...
 4 
...
 (cons 
...
 (cons 
...
 5 
...
 empty) 
...
 empty))))
...
Which notation is easier to read?
 HTML
</tr>
</td>
 HTML
 HTML
</table>
...
'
 abbreviations
Using
...

 '
 notation we can abbreviate our lists even more.
...
'
 notation is especially useful when we have nested lists.
...
'(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
<TABLE BORDER=1 BGCOLOR=#EFEFDF class="MsoBodyTextIndent">
 HTML
<CAPTION class="MsoBodyTextIndent">
Exercise
 HTML
</CAPTION>
 HTML
<td>
<tr>
 HTML
Re-write the lists from above using
...
 '
 notation.
 HTML
</td>
 HTML
</tr>
 HTML
</table>
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)))
...
<strong>
 HTML
NB:
 HTML
</strong>
 Code Block'1
 reduces to to1
 Code Block
1
 . In general,
 Code Block
'&lt;a number&gt;
 evaluates to 
 Code Block
&lt;a number&gt;
.
 HTML
<TABLE BORDER=1 BGCOLOR=#EFEFDF class="MsoBodyTextIndent">
...
'<a number>
 evaluates to<a number>
 .
 HTML
 HTML
Exercise
 HTML
</CAPTION>
 HTML
<tr>
 HTML
<td>
What do we get in these cases?
...
...
'((make-posn 
...
 1 
...
 2)) 
...
'(1 (+ 
...
 1 
...
 1) 
...
 (+ 
...
 1 
...
 1 
...
 1))
...
 HTML
</td>
 HTML
</tr>
 HTML
</table>
You cannot use list abbreviation one nested in another. For example
...

...
 '(1 
...
 '(+ 
...
 1 
...
 1)) 
...
 (will 
...
 be 
...
 treated 
...
 in 
...
 DrScheme 
...
 as
...
(smile) (list 
...
 1 
...
 (list 
...
 'quote 
...
 (list 
...
 '+ 
...
 1 
...
 1)))
...
If we want to apply functions, we have to use either cons or list eitherconsorlist. (Not exactly true. There is another abbreviation,quasiquote, that we won't talk about in this course.)
 HTML
</div>
 HTML
<div id="header">
...
 HTML
Trees & Mutually Recursive Data Definitions
 HTML
...
</div>
 HTML
<div id="content">
 HTML
<strong>
 HTML
<font color="red">
Instructions for students & labbies:
</font>
 HTML
 HTML
</strong>
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 (also 
...
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
<dfn>
parse
 HTML
</dfn>
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
<TABLE BORDER=1 BGCOLOR=#EFEFDF class="MsoBodyTextIndent">
 HTML
<CAPTION class="MsoBodyTextIndent">
...
.
 HTML
</CAPTION>
 HTML
Exercise
 HTML
<tr>
 HTML
<td>
 HTML
 HTML
<ol>
 HTML
<li>
Make more example data.
 HTML
</li>
 HTML
<li>
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.
</li>
 HTML
<li>
 HTML
 HTML
...
Challenge exercise:
 HTML
</strong>
Let's say we had many basic 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,
 and andevaluate
 Code Block
evaluate
 for this.
 As a further challenge, also allow unary operations.
 HTML
</li>
 HTML
</ol>
 HTML
</tr>
</td>
 HTML
</table>
 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
<PRE>
(define-struct dir (name contents))
...
; 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
</PRE>
This is very similar to the descendant trees data structure seen in class.
<STRONG>
 HTML
Tree-based data structures are very common!
 HTML
</STRONG>
 HTML
<CAPTION class="MsoBodyTextIndent">
<TABLE BORDER=1 BGCOLOR=#EFEFDF class="MsoBodyTextIndent">
 HTML
Directory exercises
 HTML
<TR>
</CAPTION>
 HTML
 HTML
<TD>
 HTML
<OL>
 HTML
<LI>
Create some sample data for the above types.
 HTML
</li>
 HTML
<LI>
Write the templates for the above types.
 HTML
</li>
 HTML
<LI>
Develop a function
<PRE>
 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
<TABLE BGCOLOR=#BFBFBF BORDER=1>
 HTML
 HTML
<CAPTION>
Aside
 HTML
</CAPTION>
 HTML
<TR>
 HTML
<TD>
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 find to findto see what it can do.
 HTML
</TR>
</TD>
 HTML
</TABLE>
 HTML
 HTML
<LI>
</li>
 HTML
Use DrScheme's stepper to step through an example use
 of find offind?.
 Following the templates leads to an overall strategy known as
 HTML
<DFN>
depth-first search
 HTML
</DFN>
. I.e., it explores each tree branch to the
 end before moving on to the next branch.
 HTML
</li>
 HTML
<LI>
Develop the following function:
<PRE>
 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
</PRE>
There's a straightforward way that just follows the template.
...
.
 HTML
<LI>
 HTML
 HTML
<STRONG>
Challenge:
</STRONG>
 HTML
Develop a program to check for duplicated names among
 all directories alldirectories and files in the given tree, not just
 subdirectories.
 Here's a hint.
 HTML
</li>
 HTML
<LI>
Develop the following function:
 HTML
<PRE>
; 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
</PRE>
Here are two pictorial examples, in both cases removing the directory
 named to namedto-remove. These illustrate why this function can
 return either a file or a list of files.
<TABLE BORDER=1>
 HTML
<TR>
 HTML
 HTML
<TH>
 HTML
</TH>
 HTML
...
Input
 HTML
</TH>
 HTML
<TH>
Output
 HTML
</TH>
 HTML
<TR>
</TR>
 HTML
 HTML
<TH>
Example 1:
</TH>
 HTML
<TD>
 HTML
<PRE>
 HTML
foo
 / | \
 bar baz to-remove
 / \
 one two
 HTML
</TD>
</PRE>
 HTML
<TD>
 HTML
 HTML
<PRE>
foo
 / / \ \
 bar baz one two
 HTML
</PRE>
 HTML
</TD>
 HTML
<TR>
</TR>
 HTML
 HTML
<TH>
Example 2:
</TH>
 HTML
<TD>
 HTML
<PRE>
 HTML
to-remove
 / | \
 foo bar baz
 HTML
</TD>
</PRE>
 HTML
 HTML
<TD>
 HTML
<PRE>
foo bar baz
 HTML
</PRE>
 HTML
</TD>
 HTML
</TR>
 HTML
</TABLE>
 HTML
...
Follow the templates and think about a single
 case at a time.
...
</STRONG>
 HTML
If you do that, it shouldn't be too difficult. If you don't, you'll
 probably have real trouble.
 HTML
</OL>
</li>
 HTML
 HTML
</TD>
 HTML
</TR>
 HTML
<TR>
 HTML
<TD>
 HTML
...
Sample solutions.
 HTML
</A>
 HTML
</TD>
 HTML
</TR>
 HTML
</div>
</TABLE>
 HTML
!! Access Permissions
  • Set ALLOWTOPICCHANGE = Main.TeachersComp211Group