## CMSC 15100 - Autumn 2005 Lab 5

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

• Abstracting Functions
1. Comparison: Compare and mark differences
2. Abstraction: Replace similar features by parameters
3. Redefine: Validate the abstraction by re-writing your concrete instances.
4. Contract: Write a contract which is as general as possible to cover the widest range of concrete uses.

### 1. Binary Tree Data Type

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

• A `(btree-of X)` is either
1. `empty` or
2. `(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 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.