Due: Friday, November 12 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
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
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
; Your name(s) here.
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.
To submit your homework, you must commit and push to GitHub before the deadline.
Your repository should contain the following files
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. If you’ve forgotten how to write tests, consult homework 1.
For each of these, use either
- Use a fold to write
(index x lst) which returns the 0-based index of
x is not an element of
(index 3 '(2 4 3 1 2 3)) returns
(index 3 '(2 4 6 4 2)) returns
- Use a fold to write
(replace a b lst) which replaces every instance of
(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)
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
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
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
In order to use the definitions in
tree.rkt, you need to add the line
#lang racket line at the top of
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.
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’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
tree.rtk. Take a look at that file to understand how the implementation works.
You should use
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.
(child-sum t) which returns the sum of the values in the children of
(child-sum T8) returns
(child-sum T6) returns
(child-sum empty-tree) returns
(all-sum t) which returns the sum of all of the values in
(all-sum T8) returns
(all-sum T6) returns
(all-sum empty-tree) returns
(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.
(sizeof t) which returns the number of nodes in the subtree rooted at
(sizeof T8) returns
(sizeof T6) returns
(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
(height T1) returns
(height T8) returns
(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)
(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)
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.
Make sure you commit and push.