Page History

...

; 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) ... ) ...]))

...

Finger Exercises on List Abbreviations

1. Evaluate he the 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)))

2. 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)

...

Finger Exercises on list constants

1. Evaluate he the 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.

...

In class, we used ancestor family trees as an example of inductively defined tree data. In ancestor family trees, each person (a make-child structure) has two ancestors (also make-child structures) which may be empty. In this lab, we'll use a similar, but slightly different, form of tree as an example.

In mathematics, we can use formalized arithmetic expressions as trees. For example,

...

;; Given

(define-struct add (mleft nright)) 
(define-struct sub (mleft nright)) 
(define-struct mul (mleft nright)) 
(define-struct div (mleft nright)) 

;; an Arithmetic-Expression (AExp) is either:
;; - a number ;
;; - (make-add ml nr) where ml,nr are AExps;
;; - (make-sub ml nr) where ml,nr are AExps; 
;; - (make-mul ml nr) where ml,nr are AExps; or
;; - (make-div ml nr) where ml,nr are AExps,

Using this data definition, the arithmetic expression above corresponds to the structure ae1 defined by

...

1. 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.
2. Wiki Markup\[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, extend your data definition to accommodate unary operations including negation and absolute value as unary operators.

Files and Directories

The following are data definitions are idealized (for the sake of simplicity) representations of files and directories (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 in the definition of a file, which makes the set f definitions more compact but obfuscates 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.

...

1. Create some sample data for the above types.
2. Write the templates for the above types.
3. Develop a function

   Code Block
   ; 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.

   (empty line) Note that this function is a vast simplification of{{find}}, the mother-of-all everything-but-the-kitchen-sink UNIX directory traversing command. If open a terminal window and enter

   Code Block
   man find

   to see what it can do.
   (empty line)
   
   Use DrScheme's stepper to step through an example use of find?. Following the templates leads to an overall strategy known as depth-first search, i.e., it explores each tree branch to the end before moving on to the next branch.
4. Develop the following function:

   Code Block
   ; 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.

   (empty line) There is a straightforward way to write this function that just follows the template. (empty line)
5. Challenge: develop a program to check for duplicated names among
   all directories and files in the given tree, not just subdirectories.
   
   Here's a hint. Develop the following function:

   Code Block
   ; flatten-dir-once : symbol file -> (file or lof)

   
   

   ; Purpose: returns a structure like the original file, except that any (sub)directory with that name is removed and its contents are promoted up one level in the tree.

   (empty line)
   Here are two pictorial examples, in both cases removing the directory
   namedtonamed to-remove. These illustrate why this function can
   return either a file or a list of files.

Example 1:

foo
/ \ \
bar baz to-remove
/ \
one two

becomes

foo
/ / \ \
bar baz one two

...

Example 2:

...

to-remove
/ \ \
foo bar baz

becomes

...

      foo
    / \   \
 bar baz to-remove
          / \
        one two

becomes

      foo
   /  / \  \
bar baz one two

...

Example 2:

...

 to-remove
   / \ \
foo bar baz

becomes

foo bar baz

Follow the templates and think about a single

...

case at a time. If you do that, this exercise is not too difficult. If you don't follow the templates, you

...

are likely to run into difficulty.