Day 22 - Intro to trees & Trees as recursive data

Skills: 6

Pre-reading: 7.1.1, 7.1.2

Supplementary Videos

Intro (20 mins)

Today we introduce trees—a way to represent hierarchical data where each item can have sub-items.
Real-world example: a river network, where streams merge into larger streams and rivers.
Tables can't easily represent this branching structure—each merge point connects to exactly two upstream sources.
We can model this as a binary tree (which are the simplest form of tree), where each node has two sub nodes. Trees are similar to lists, in that they are conditional data where one case is the end (or base) and the other is a recursive case, but unlike lists, the recursive case has multiple self-referential fields -- below, left and right.

River network as conditional data:

data River:
  | merge(width :: Number, left :: River, right :: River)
  | stream(flow-rate :: Number)
end

# Example: A small river network
stream-a = stream(5)
stream-b = stream(8)
stream-c = stream(3)
merge-1 = merge(12, stream-a, stream-b)
main-river = merge(15, merge-1, stream-c)

As with NumLists from Day 21, we can also come up with a template for designing functions with Rivers:

#|
fun river-fun(r :: River) -> ???:
  cases (River) r:
    | merge(width, left, right) =>
      ... width ...
      ... river-fun(left) ...
      ... river-fun(right) ...
    | stream(flow) => ... flow ...
  end
end
|#

Example function: calculate total flow in a river network

fun total-flow(r :: River) -> Number:
  cases (River) r:
    | merge(width, left, right) => total-flow(left) + total-flow(right)
    | stream(flow) => flow
  end
where:
  total-flow(stream-a) is 5
  total-flow(main-river) is 16
end

Example function: count merge points in a river network

fun count-merges(r :: River) -> Number:
  cases (River) r:
    | merge(width, left, right) => 1 + count-merges(left) + count-merges(right)
    | stream(flow) => 0
  end
where:
  count-merges(stream-a) is 0
  count-merges(main-river) is 2
end

Class Exercises (35 mins)

Design a function count-streams that counts how many individual streams feed into a river network.
Design a function max-width that finds the maximum width among all merge points in a river network.
Design a function widen-river that takes a river network and a number, and returns a new network where every merge point is wider by that amount.
Design a function cap-flow that takes a river network and returns a new network where no stream has flow-rate above 10 (cap any higher values at 10).
Design a function has-large-stream that returns true if any stream in the network has flow-rate greater than 6.

Wrap-up (5 mins)

Binary trees naturally represent branching structures like river networks.
Recursive data definitions with multiple variants capture tree structure.
Recursive functions use cases to handle each variant appropriately.
Tree processing often follows patterns: reductions (sum, count) and transformations (map-like operations).

Skills: 6​

Pre-reading: 7.1.1, 7.1.2​

Supplementary Videos​

Intro (20 mins)​

Class Exercises (35 mins)​

Wrap-up (5 mins)​