Assignment 5 - Structured Data

Structured & conditional data

#

Read §6.1 in DCIC.

Revisiting bar weights

#

We’re going to rewrite and expand our bar-weight function from an earlier assignment using structured data. Start by creating a file weightlifting2.arr.

1. Create a variable data type Bar, that can be womens-olympic, mens-olympic, trap, squat-safety, or swiss.

2. Write a function bar-weight that consumes a single variable bar of type Bar and produces the weight of that bar in kg, using the following:

3. Create a variable data type Plate, that can be red, blue, yellow, green, white, black, or custom(weight :: Number) (a custom weight).

4. Write a function plate-weight that consumes a single variable plate of type Plate and produces the weight of that plate in kg, using the following:

5. Write a function weight-in-pounds that consumes a Bar and a list of Plates and produces the weight in pounds of that bar loaded with that list of plates, using the conversion rate of 1 kg = 2.2 pounds.

The type signature should be the following:

fun weight-in-pounds(bar :: Bar, plates :: List<Plate>) -> Number

Optional challenge 1.¹ Write a function choose-plates that determines the plates to add to a bar to achieve a certain weight in kilograms.

fun choose-plates(bar :: Bar, weight-kg :: Number) -> List<Plate>

Your program should add plates in pairs, and should always prefer the heaviest available plates, ending with custom plates only if no other plates can be added.

Recursive data & Trees

#

The data definition for a List looks like this:

data List:
  | empty
  | link(first :: Any, rest :: List)
end

This is recursive: one of the fields of a List is itself a List.

Now consider the definition of a “tree”:

data Tree<V>:
  | leaf
  | branch(value :: V, left :: Tree<V>, right :: Tree<V>)
end

This is just like a List, but instead of having one recursive rest it has two recursive parts, a left and right that are both Trees.

Here’s an example of a tree.

         1
        / \
       2   3
      / \
     4   5

To represent this in our code, we would write:

branch(1,
	branch(2,
		branch(4, leaf, leaf),
		branch(5, leaf, leaf)),
	branch(3, leaf, leaf))

We can write a function that counts the number of elements in a tree as follows.

fun tree-size(t :: Tree) -> Number:
  doc: "counts the number of elements in a tree"
  cases (Tree) t:
    | leaf => 0
    | branch(v, l, r) => 1 + tree-size(l) + tree-size(r)
  end
where:
  tree-size(leaf) is 0
  tree-size(branch("hi", branch("hello", leaf, leaf), leaf)) is 2
end

Create a file called trees.arr.

1. Write a function tree-sum that sums all the values in a tree of numbers.

2. Write a function tree-height that finds the height of a tree. The height of a tree is the longest path that exists from the root (first element) of the tree to any one non-leaf node, or zero if the tree is a leaf. For example, the height of our example tree above is 3.

3. Write a function tree-equal that determines whether two trees are equal.

Optional challenge 2.² Write a function is-tree-subtree that determines whether one tree is a subtree of another tree. A tree is a subtree of another if the first appears somewhere in the other. For example, the following are all subtrees of the example tree above:

   1          2        1        1      (leaf)
  / \        / \        \       
 2   3      4   5        3       

(A tree is also a subtree of itself.)

Turn in

#

Download weightlifting2.arr and trees.arr and submit them to gradescope.