CMSC 15100 - Autumn 2005
Lab 5

Save a copy of this lab for yourself

Extra Credit problems are in red!!

0. Abstraction

In this lab you will be using the design recipe to abstract from function definitions on Binary Trees. Follow the Design Recipe carefully.

1. Binary Tree Data Type

A btree, or binary-branching tree, will be given a parametric data definition, just as we had with list:

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

;; 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 cube-values and 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.

;; 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 btree-map. 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)
;; Replace the value-list with the sum-of-values in btree
;; (define (sum-values btree) ...)

 Keep your code short!! Use abstract list functions.

;; scale-values: (btree-of number) number -> (btree-of number)
;; multiply each value by n
;; (define (scale-values btree n) ... )

 Use lambda abstraction for shorter, cleaner code.

;; 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 halve-evens and replace-empty-values suggest a new abstraction, btree-filter-map. I have written a contract of this function appropriate for halve-evens. Write a more general contract applicable to replace-empty-values and write the body using btree-map:

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

Test btree-filter-map by writing halve-evens and replace-empty-values using this function.

Write btree-map using btree-filter-map. 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 list template. We can do the same thing with the template for btree.

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

3b. Btree-fold

A btree is a conditional data type, with two conditions. What did you have to do for each condition in writing sum-all-values and all-true?? If btree was empty you had no constituent parts of btree to use, so in this case you had to just return a base value. In the 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 abstraction, btree-fold. (See HTDP, where the function is called reduce.)

;; 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 btree-fold. Redefine the functions from 3a using your abstract tree function.

3c. Concrete Examples

Define the following functions using btree-fold. Modify your contract for btree-code to ensure it covers these cases.

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

enumerate is useful. Write the following function using your enumerate and 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

Re-write btree-map using btree-fold. Make sure your contract for btree-fold is sufficiently general to cover this case as well.