Day 22 - Trees as recursive data

Skills: 6

Pre-reading: 7.1.2

Intro (10 mins)

• Yesterday, we saw how trees can represent hierarchical data like organizations.
• Today, we’ll see how to define trees as recursive data, and how this lets us write powerful recursive functions.
• Example:

  data OrgTree:
    | node(name :: String, title :: String, reports :: List<OrgTree>)
  end
  
  # Example: A small organization
  dave-tree = node("Dave", "Engineer", empty)
  frank-tree = node("Frank", "Engineer", empty)
  bob-tree = node("Bob", "CTO", [list: dave-tree, frank-tree])
  eve-tree = node("Eve", "Accountant", empty)
  carol-tree = node("Carol", "CFO", [list: eve-tree])
  alice-tree = node("Alice", "CEO", [list: bob-tree, carol-tree])

Class Exercises (35 mins)

Given the OrgTree data definition and the example trees above:

1. Leaf Check: Write a function is-leaf that takes an OrgTree and returns true if the node has no reports, false otherwise.
2. List All Titles: Write a function all-titles that returns a list of all titles in the organization tree (duplicates are okay).
3. Count by Title: Write a function count-title that takes an OrgTree and a title, and returns the number of employees with that title.
4. Promote All: Write a function promote-all that takes an OrgTree and a function from String -> String, and returns a new tree where every title has been updated by the function.
5. Find Employee: Write a function find-employee that takes an OrgTree and a name, and returns the OrgTree node for that employee, or empty if not found.
6. Tree Height: Write a function org-height that returns the number of levels in the organization tree (root is level 1).
7. Find Path to Employee: Write a function find-path that takes an OrgTree and a name, and returns a list of names showing the path from the root to that employee (or empty if not found).

Wrap-up (5 mins)

• Recursive data definitions let us naturally express and process hierarchical data.
• Recursive functions mirror the structure of the data.
• Next time: more tree traversals and transformations.