Homework 4: Folds & Trees

Due: Friday, October 11 at 23:59
First Commit: Monday, October 7 at 23:59

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

Again, I reserve the right to deduct points on the implementation here if there are no higher-order functions used.

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. The same partnership and team making procedures apply as previous assignments!

If you need a reminder of the procedures, 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. It’s extremely helpful for the graders if you include your name and your partner’s name in the team name. Unfortunately, you cannot use the same team name for multiple assignments. You can append the homework number to your team name if you wish. (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 in Racket Fundamentals.

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
• tree.rkt
• HONORCODE.md

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 main branch. (You’re free to make other branches, if you desire, but make sure main 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. For Part 1, make sure you write at least two tests for each function. Make sure your tests are exercising different circumstances!

To receive full credit on problems 1 through 3, use either foldl or foldr.

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)

A list consisting of elements, each of which is itself a list, representing the data for one individual is called an association list in Racket. See the example below:

   (define bags
     '((duffle 8)
       (garment-bag 2)
       (briefcase 5)
       (valise 7)
       (steamer-trunk 65)))

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. You will need to define your own test association list in tests.rkt (not in hw4.rkt) to be able to reference it in your tests. This should be outside of a test-suite definition.

Racket has a standard library function assoc which is designed to work with association lists. For this assignment, do not use it in your implementations.

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

If you haven’t already done so recently, now would be a great time to commit all of your code and push it to GitHub. Recall that you need to first add the files, commit them, and then push. If you’re using Github Desktop, go through the similar steps.

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 tree.rkt – you must use this structure to obtain full credit on this assignment. Again, a note that the trees as part of this assignment are not necessarily binary trees.

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

(require "tree.rkt")

below the #lang racket line at the top of hw4.rkt (remember our discussion of modules in Lecture 11!).

This particular implementation represents an empty tree as null. 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 nonempty 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 is 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 tree.rkt. Take a look at that file to understand how the implementation works.

For Part 2, you are expected to use map, apply, and fold to make your solutions concise. All of your procedures should be written using the tree operations defined above. Do not directly manipulate the list representation, you will not get credit for these implementations. 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. Full credit for tests for Part 2 will be obtained if:

• You write at least two meaningful tests for each procedure
• Assume that all trees are numerical trees (i.e. trees which contain numbers as values). This is true of all the provided trees as well.
• At least one test for each procedure should reference a test tree of your own development that is defined in tests.rkt. This needs to be at least one, if not multiple, totally new trees with different structure than the examples provided. A reminder our tree implementation works for non-binary trees!

1. Write (child-sum t) which returns the sum of the values in the (immediate) children of t.
   • (child-sum T8) returns 173
   • (child-sum T6) returns 82
   • (child-sum empty-tree) returns 0
2. 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

3. 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 been replaced with (f v). For example, (visit-tree add1 t) increments every value in t by 1.

4. Write (size-of t) which returns the number of nodes in the subtree rooted at t.
   • (size-of T8) returns 8
   • (size-of T6) returns 4
   • (size-of empty-tree) returns 0
5. 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 on.
   • (height empty-tree) returns -1
   • (height T1) returns 0
   • (height T8) returns 2
6. Pick one of the following tree traversals to implement, either a pre-order traversal or a post-order traversal. You will only receive full credit if your procedure name matches the traversal it returns. Some potential tests you may want to consider:
   • (pre-order T8) returns '(16 73 50 22 10 100 5 17)
   • (post-order T8) returns '(50 22 10 73 5 17 100 16)

Common Questions

• When there are multiple bags with the same weight (i.e. '((pen 2) (pencil 2))), which should heaviest return? The first instance in the association list.

• Do we have to handle non-tree arguments to tree methods in Part 2? No, assume the original input is a tree. You do need to handle empty trees and single element trees though.

• Can we use flatten? flatten as you have previously written it is an operation on lists, not trees. You can write a flatten-tree helper, if you’d like.

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.

Once you have finished (or better yet, frequently as you’re working!), you need to push your code to GitHub. Make sure to double check that you’ve included your name and the name of your partner (if you’re working with a partner) in all files, check that you’ve completed the honor code, and then add/commit/push.

$ git add hw4.rkt tests.rkt tree.rkt HONORCODE.md
$ git commit
$ git push