Save a copy of this lab for yourself
- Language: Intermediate Student with Lambda Expressions
- Teachpack: none
- Lab 5 Template (scm) Change the name of this template file using your CNET ID.
In this lab you will be using the design recipe to abstract from function definitions on Binary Trees. Follow the Design Recipe carefully.
- Abstracting Functions
- Comparison: Compare and mark differences
- Abstraction: Replace similar features by parameters
- Redefine: Validate the abstraction by re-writing your concrete instances.
- Contract: Write a contract which is as general as possible to cover the widest range of concrete uses.
1. Binary Tree Data Type
btree, or binary-branching tree, will be given a
parametric data definition, just as we had with
(btree-of X)is either
(make-btree X (btree-of X) (btree-of X))
(define-struct btree (value left right))
1a. Btree Template
Write a template for a function with a
btree as argument.
1b. Cube-Values on Btree
Use good programming practice in every program you write. Follow Design
;; cube-values: (btree-of number) -> (btree-of number)
;; cube the values of btree
;; (define (cube-values btree) ... )
1c. Reverse-Values on Btree
;; reverse-values: (btree-of (listof symbols)) -> (btree-of (listof symbols))
;; reverse the lists on btree. (reverse is built-into Dr. Scheme)
;; (define (reverse-values btree) ...
2. Abstracting From Examples
2a. Binary Tree Map
Write a new function which abstracts from
reverse-values. Follow the four steps of the abstraction
recipe from Part 0. Try to write a general contract, but remember
you can modify it later. Just make sure that the contract
is appropriate every time you use
;; btree-map: ??? -> ???
Do not forget to redefine your function on the concrete examples.
2b. More Concrete Test Cases
Each of the following functions must be written using
Remember, that the contract of
btree-map must match that of
the concrete instances. You may have to revise your contract.
;; sum-values: (btree-of (listof number)) -> (btree-of number)
Keep your code short!! Use abstract list functions.
;; Replace the value-list with the sum-of-values in btree
;; (define (sum-values btree) ...)
;; scale-values: (btree-of number) number -> (btree-of number)
Use lambda abstraction for shorter, cleaner code.
;; multiply each value by n
;; (define (scale-values btree n) ... )
;; halve-evens: (btree-of number) -> (btree-of number)
;; If value is even, then halve it
;; (define (halve-evens btree) ...)
;; replace-empty-values: (btree-of (listof symbol)) -> (btree-of (listof symbol)
;; replace each value which is an empty list-of-symbols
;; by the the list-of-symbol (list 'none)
;; Ex. (make-btree empty empty empty) --> (make-btree (list 'none) empty empty)
;; (define (replace-empty-values btree) ... )
2c. Abstract Test Case
The last two examples
a new abstraction,
btree-filter-map. I have written
a contract of this function appropriate for
Write a more general contract applicable to
and write the body using
;; btree-filter-map: (number-> boolean) (number-> number) (btree-of number)
-> (btree-of number)
;; apply the function op to every value for which P? is true
;; (define (btree-filter-map P? op btree) ... )
btree-filter-map by writing
replace-empty-values using this function.
Do not try to re-write
btree-filter-map without using
btree-map, but it would be good experience to write this
function by abstraction without using the map operation.
3. Abstracting from the Template
In class we designed
foldr by abstracting from the
We can do the same thing with the template for
3a. Concrete Instances
Start with your template from Part 1a and write definitions for the
following functions. Pay careful attention to what how you fill-in
the ellipses ("...") in your template.
;; sum-all-values: (btreeof number) -> number
;; sum over all values in btree
;; (define (sum-all-values btree) ...)
;; all-true?: (btree-of boolean) -> boolean
;; Are all values true?
;; All values an empty btree are true!
;; (define (all-true? btree) ... )
btree is a conditional data type, with two conditions.
What did you have to do for each condition in writing
empty you had no constituent parts
btree to use, so in this case you had to just return a
else case the
btree had constituent
parts which had to be combined to produce a value. When you
abstract from the template you need to replace the base value
and the combination function with parameters to your
(See HTDP, where the function is called
;; btree-fold: ??? ->???
;; abstraction from the template
;; (define (btree-fold combine base btree) ... )
Take a stab at what the contract should be, but you can fix it as you look at examples using
the functions from 3a using your abstract tree function.
3c. Concrete Examples
Define the following functions using
your contract for
btree-code to ensure it covers these
;; count-nodes: (btree-of X) -> number
;; count nodes on tree
;; (define (count-nodes btree) ...)
;; enumerate: (btree-of X) -> (listof X)
;; produce a list of values
;; (define (enumerate btree) ... )
What order did you enumerate your values in the list. Did you place the node-value first? Did you place it last? Did you place it between the values in the left-branch and right-branches? Suppose your
btree were a binary search tree, then what order is
appropriate if you want your list of values to be in order?
(Hint: Remember the binary search tree
enumerate is useful. Write the following function using
abstract list functions
;; btree-filter: (X->bool) (btree-of X) -> (listof Y)
;; Construct a list of values from all those on Btree
;; for which P?
3d. Abstract Examples
sure your contract for
btree-fold is sufficiently
general to cover this case as well.