Lab 5: Call the Plumber,
or, A Tree by Any Other Name

16 February 2024

Learning objectives

The purpose of this lab is to give you practice:

  • modeling parts of the world using trees,
  • working with structurally recursive data definitions, and
  • writing functions using a template for structurally recursive data definitions.



We would like to write a program that represents pipelines, as you might do if you were building a computer model of real-world infrastructure – or if you were making a game like SimCity!

A pipeline has

  • faucets, which can be opened or closed,
  • faucet open faucet closed
  • straight pipes, which can be copper or lead,
  • one straight pipe
    leading to a faucet
    two straight pipes
    leading to a faucet
  • and branches, where a pipe splits in two.
  • pipeline with one branch pipeline with several branches

Data definition

We can represent pipelines as described above with the appropriate data definition. Since our pipelines consist of multiple instances of faucets, straight pipes, and branches, our data definition includes these three varieties.

Task: Copy the following data definitions and examples into your lab05.arr file.

data Pipeline:
  | faucet(is-open :: Boolean)
  | straight(kind :: Metal, pl :: Pipeline)
  | branch(pl1 :: Pipeline, pl2 :: Pipeline)

data Metal:
  | lead
  | copper

# Examples of pipelines
f-closed = faucet(false)
f-open = faucet(true)

straight-c = straight(copper, f-closed)

straight-c-l =
    straight(lead, f-closed))

branching-pipeline =
      straight(copper, f-open),


Since we defined a new type of data (Pipeline), it’s a good idea to write a template we can use for functions that take that data as input.

Task: Copy this template into your lab05.arr file.

fun pipeline-fun(pl :: Pipeline) -> ...:
  doc: "Template for a function that takes a pipeline"
  cases (Pipeline) pl:
    | faucet(is-open) =>
      ... is-open ...
    | straight(kind, pl1) =>
      ... kind ...
      ... pipeline-fun(pl1) ...
    | branch(pl1, pl2) =>
      ... pipeline-fun(pl1) ...
      ... pipeline-fun(pl2) ...
  pipeline-fun(...) is ...

# Exercise 1

# Exercise 2

# Exercise 3

# Exercise 4

# Exercise 5

Exercise 1

Task: Implement the function is-water-running, which takes a Pipeline and determines whether any faucets are open.

To help you get started with the lab, we’ve done this one for you!

# Exercise 1

fun is-water-running(pl :: Pipeline) -> Boolean:
  doc: "Determine whether any faucets are open in pl"
  cases (Pipeline) pl:
    | faucet(is-open) =>
    | straight(kind, pl1) =>
    | branch(pl1, pl2) =>
      is-water-running(pl1) or is-water-running(pl2)
  is-water-running(f-open) is true
  is-water-running(f-closed) is false
  is-water-running(straight-c) is false
  is-water-running(straight-c-l) is false
  is-water-running(branching-pipeline) is true

Copy and paste it into your lab05.arr file. Make sure you understand how this function works – how did we write this based on the template above?

Task: Why do we have so many examples for this function? Since it’s a predicate (a function returning a Boolean), why isn’t it enough to have one true example and one false example? Put your answer in a comment.

Exercise 2

Task: Implement the function count-faucets, which takes a Pipeline and counts the number of faucets it contains.

To do this,

  • Copy and paste the template.
  • Fill in
    • the desired function name (everywhere it occurs),
    • the docstring, and then
    • the examples.
  • Using the examples, replace the placeholders (...) in the template with appropriate code.

Exercise 3

Task: Implement the function count-open, which takes a Pipeline and counts the number of open (that is, running) faucets.

Follow the same steps!

Exercise 4

Task: Implement the function modernize, which takes a Pipeline and converts all the (straight) lead pipes to copper ones.

Hint: You don’t need an if to do this!

Exercise 5

Task: Implement the function off, which takes a Pipeline and turns off all the faucets.

Submitting the lab

  • When you’ve completed the exercises, show your code to your instructor or one of the coaches.
  • Then upload your lab05.arr file to the Lab 5 assignment on Gradescope. If you worked with a partner, you should submit a single copy of the lab with both your names – see these instructions.