Page History

h2. 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.


h3.

 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

}
; 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

}
; 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

h4. 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.

h4. 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}
(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)))

{code}

# Rewrite the following using {{list}}.
{code}
(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)

We can think of the {{'}} operator as distributing over the elements. We apply this rule recursively until there are no more {{'}} operators left.  This simple rule makes embedded references to {{true}}, {{false}}, and {{empty}} behave strangely because {{'true}}, {{'false}}, and {{'empty}} reduce to _themselves_ as _symbols_, not to {{true}}, {{false}}, and {{empty}}.  In contrast, {{'n}} for some number {{n}} reduces to {{n

{code

}
(+ 5 (* (- 1 8) (+ 7 1)))
{code}
which encodes expressions as lists revealing their nesting structure.

 

The string representation for expressions is particularly unattractive for computational purposes because we have to

parse the string to understand its structure. The parsing process must understand which symbols are variables, operatorsj incorporate the precedence of infix operators.

We can define a tree formulation of simple Scheme expressions which avoids representing them as list and encodes far more information about their structure.  Parsers build tree representations for programs.

To simplify the formulation of Scheme expressions as trees,

 
we will limit each addition, subtraction, multiplication, and

division operation to exactly two subexpressions.  We will limit the

atomic elements of expressions to numbers.

{code

}
;; Given

(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 either:

;; - 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; or

;; - (make-div <var>m</var> <var>n</var>) where <var>m</var>,<var>n</var> are AExps,

{code}

Usinbg this data definition, the

 arithmetic expression above corresponds to the structure {{ae1}}
defined by
{code}
(define ae1 (make-add 5 (make-mul (make-sub 1 8) (make-add 7 1))))

{code}
A trival {{AExp}} is {{ae2}} defined by
{code}
(define ae2 16)
{code}

h4. Exercises on Arithmetic Expressions

# Develop the function {{eval: AExp -> N}} where {{(eval ae)}} returns the number denoted by the expression
{{ae}}.  For example,
{{(eval ae1)}}
should return {{\-51}}, and
{{(eval ae2)}}
should return {{16}}.

# /[Challenge/] Assume that our expression language includes many basic operations, not just
the four supported by {{AExp}}.  We would want a single representation for the application
of a binary operator to arguments and use a separate data definition enumerating
all of our operations. Rewrite the preceding data definitions, examples,
and the function {eval} using 
for this.
As a further challenge, also allow unary operations.
{html}{html}
{html}{html}
{html}{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.

; 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}{html}




This is very similar to the descendant trees data structure seen in class.
{html}{html}Tree-based data structures are very common\! {html}{html}






{html}{html}
{html}{html}Directory exercises
{html}{html}
{html}{html}
{html}{html}
{html}{html}
{html}{html}Create some sample data for the above types.
{html}{html}
{html}{html}Write the templates for the above types.
{html}{html}
{html}{html}Develop a function
{html}{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}{html}
{html}{html}Aside {html}{html}


{html}{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}
{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}{html}. I.e., it explores each tree branch to the

end before moving on to the next branch.

{html}{html}
{html}{html}Develop the following function:
{html}{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}{html}
{html}{html}
{html}{html}Challenge: {html}{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}
{html}{html}Develop the following function:

{html}{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}{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}{html}
{html}{html}
{html}{html}Input {html}{html}
{html}{html}Output {html}{html}
{html}{html}
{html}{html}
{html}{html}Example 1: {html}{html}
{html}{html}
{html}{html}foo
/ \| \
bar baz to-remove
/ \
one two
{html}{html}
{html}{html}
{html}{html}
{html}{html}foo
/ / \ \
bar baz one two
{html}{html}
{html}{html}
{html}{html}
{html}{html}
{html}{html}Example 2: {html}{html}
{html}{html}
{html}{html}to-remove
/ \| \
foo bar baz
{html}{html}
{html}{html}
{html}{html}
{html}{html}foo bar baz
{html}{html}
{html}{html}
{html}{html}
{html}{html}

{html}{html}Follow the templates and think about a single
case at a time. {html}{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}{html}
{html}{html}
{html}{html}
{html}{html}Sample solutions. {html}{html}
{html}{html}
{html}{html}
{html}{html}
{html}{html}

h2. \!\! Access Permissions

* Set ALLOWTOPICCHANGE = Main.TeachersComp211Group