Homework 4: More higher-order functions

Due: 2020-10-08 at 23:59

The goal for this assignment is to practice using folds and working with data structures. There are many ways to implement these functions. Using foldl, foldr, map, and apply can make your solutions more concise.

Your implementations of the following functions should all be placed in a single Racket file named hw4.rkt. The corresponding tests for each function should be in a second Racket file named tests.rkt.

You may use the solution to any exercise as a helper function in subsequent exercises and you may also write stand-alone helper functions.

The start of each file should be

#lang racket
; Your name(s) here.

Preliminaries

Click on the assignment link. If you’re working with a partner, one partner should create a new team. The second partner should click the link and choose the appropriate team. (Please don’t choose the wrong team, there’s a maximum of two people and if you join the wrong one, you’ll prevent the correct person from joining.)

Once you have accepted the assignment and created/joined a team, you can clone the repository on your computer by following the instruction and begin working. But before you do, read the entire assignment and be sure to check out the expected coding style from the first homework.

Be sure to ask any questions on Piazza.

Submission

To submit your homework, you must commit and push to GitHub before the deadline.

Your repository should contain the following files

hw4.rkt
tests.rkt
TreeDatatype.rkt

It may also a .gitignore file which tells Git to ignore files matching patterns in your working directory.

Any additional files you have added to your repository should be removed from the master branch. (You’re free to make other branches, if you desire, but make sure master contains the version of the code you want graded.)

Make sure you put your name (and your partner’s name if you’re working with one) as a comment at the top of each file.

Part 1. Folds

For each function, write the function and a test suite and add the test suite to the all-tests test suite. You might want to write the tests first. If you’ve forgotten how to write tests, consult homework 1.

For each of these, use either foldl or foldr.

Use a fold to write (index x lst) which returns the 0-based index of x in lst or -1 if x is not an element of lst.
- (index 3 '(2 4 3 1 2 3)) returns 2
- (index 3 '(2 4 6 4 2)) returns -1
Use a fold to write (replace a b lst) which replaces every instance of a with b.
- (replace 3 5 '(1 2 3 5 4 3 2 1)) returns '(1 2 5 5 4 5 2 1)
- (replace 3 5 '(2 4 6 8)) returns '(2 4 6 8)
Assume bags is globally defined to be an association list containing sublists of two elements. Each sublist represents the name of a piece of luggage and its respective weight where the first element is the name of the piece of luggage and the second element is its weight. For example, we might have
```
(define bags
  '((duffle 8)
    (garment-bag 2)
    (briefcase 5)
    (valise 7)
    (steamer-trunk 65)))
```
Using a fold, write a procedure (weigh bags) which takes a baggage list and returns the total weight.
- Given the list shown, (weigh bags) returns 87
Using a fold, write a procedure (heaviest bags) which returns the name of the bag with the largest weight where bags is an association list as described in (3). You may assume no bag has negative weight.
- Given the list shown in (3), (heaviest bags) returns 'steamer-trunk

Part 2. Trees

In this part, you will write a number of procedures that involve trees. Recall that a tree is a data structure that is either empty or contains some data and has a list of children, each of which is a tree.

I have provided a definition of a tree data structure in the file TreeDatatype.rkt.

In order to use the definitions in TreeDatatype.rkt, you need to add the line

(require "TreeDatatype.rkt")

below the #lang racket line at the top of hw4.rkt.

This particular implementation represents an empty tree as null. (This is the same representation as the empty list.) For clarity, empty-tree is defined as null and can be used to denote an empty tree.

(define empty-tree null)

A new tree can be constructed from a value and a list of children.

(tree value (list child-1 child-2 ... child-n))

For convenience, there’s another constructor.

(make-tree value child-1 child-2 ... child-n)

There are two recognizers that you’ll find extremely useful.

(empty-tree? t) ; Returns #t if t is an empty tree
(tree? t)       ; Returns #t if t is a tree

Three are two accessor procedures which, when given a tree, return the value and the list of children, respectively.

(tree-value t)    ; Returns t's value
(tree-children t) ; Returns t's list of children

There’s a utility procedure which returns #t when the given tree is a leaf (has no children).

(leaf? t) ; Returns #t if t has no children

Finally, there are eight example trees defined

(define T1 (make-tree 50))
(define T2 (make-tree 22))
(define T3 (make-tree 10))
(define T4 (make-tree 5))
(define T5 (make-tree 17))
(define T6 (make-tree 73 T1 T2 T3))
(define T7 (make-tree 100 T4 T5))
(define T8 (make-tree 16 T6 T7))

All of this code is in TreeDatatype.rtk. Take a look at that file to understand how the implementation works.

You should use map, apply, and fold to make your solutions concise. All of your procedures should be written using the tree operations defined above. Don’t directly manipulate the list representation. As usual, if the solution to an earlier problem is useful in a later one, you may use it.

As with Part 1, write tests for each of these functions in addition to implementing them.

Write (child-sum t) which returns the sum of the values in the children of t.
- (child-sum T8) returns 173
- (child-sum T6) returns 82
- (child-sum empty-tree) returns 0
Write (all-sum t) which returns the sum of all of the values in t.
- (all-sum T8) returns 293
- (all-sum T6) returns 155
- (all-sum empty-tree) returns 0
Write (visit-tree f t) where f is a function of one numerical variable. This returns a new tree with the same structure only every value v in the tree has be replaced with (f v). For example, (visit-tree add1 t) increments every value in t by 1.
Write (sizeof t) which returns the number of nodes in the subtree rooted at t.
- (sizeof T8) returns 8
- (sizeof T6) returns 4
Write (height t) which returns the height of the tree, the maximum number of edges from the root to the leaf. The empty tree has height -1, a leaf has height 0, and so forth.
- (height empty-tree) returns -1
- (height T1) returns 0
- (height T8) returns 2
Write (preorder t) which returns a flat list of values in the tree that would result from a pre-order traversal.
- (preorder T8) returns '(16 73 50 22 10 100 5 17)
Write (postorder t) which returns a flat list of values in the tree that would result from a post-order traversal.
- (postorder T8) returns '(50 22 10 73 5 17 100 16)

Finishing up

Make sure you wrote tests of all of these, the test suite for each function is included in the all-tests test suite, and your tests pass. For reference, my solution involves 36 tests in total and when I run (test/gui all-tests), I get this.
RackUnit tests

Make sure you commit and push.