Dependency order

With the capabilities chosen (dive 1), the order between them is not free. One rule fixes it: each rung may depend only on the rungs below it. Stated precisely, a ladder r₁ … rₙ is in dependency order when, for every rung rᵢ, every rung it depends on already appears below it — deps(rᵢ) ⊆ {r₁, …, rᵢ₋₁}. That is exactly a topological order of the dependency graph.

The consequence is that value accrues bottom-up. Rung 1 is usable on its own; rung 2 adds to it; each higher rung extends what is already there. So the lowest-numbered rungs are the foundation, and a single edge that points upward — a rung that depends on something not yet below it — breaks the order. The ladder stops being a ladder the moment one dependency points the wrong way.

Two sorts pull on the ladder, and they are not the same. By dependency is the hard constraint: a rung cannot precede something it needs, or it cannot be built. By value is the soft preference: ship the most valuable usable rung first. They reconcile by precedence — dependency wins where they conflict, and value chooses the order only among rungs that do not depend on each other. A topological sort that breaks ties by value gives both.

Reorder the four rungs below to test an order. A permutation that keeps every dependency below its rung is a valid ladder; one that lifts a rung above a rung it depends on is a violation — the checker names the first offending rung and paints it burgundy. The landing read a fixed ladder bottom to top; here the order can be broken on purpose, so the violation surfaces. That is the difference between reading a ladder and checking one.

On the Portal — the learning platform this course builds — the dependency graph is a chain: browse ← enrol ← open lesson ← track progress, each arrow reading “depends on”. Because the graph is a chain, the topological order is total: the only order that builds is browse, enrol, open a lesson, track progress. Swap any adjacent pair and a dependency points upward. Put enrol before browse, and enrol depends on a rung not yet below it — the order is no longer a ladder.

Dependency order is a predicate over a candidate order. The predicate walks the order and, for each rung, confirms every dependency already appears strictly below it.

# The Portal dependency graph — a chain. Each rung lists what it depends on.
deps = %{browse: [], enrol: [:browse], open: [:enrol], track: [:open]}

valid_order? = fn order ->
  Enum.with_index(order)
  |> Enum.all?(fn {rung, i} ->
    below = Enum.take(order, i)            # rungs strictly below this one
    Enum.all?(deps[rung], &(&1 in below))  # every dependency is below
  end)
end

valid_order?.([:browse, :enrol, :open, :track])   # => true
valid_order?.([:enrol, :browse, :open, :track])   # => false — enrol needs browse below it

Dependency order is the rule that each rung depends only on the rungs below it, which makes the ladder a topological order of the dependency graph and means value accrues from the bottom up. Two sorts reconcile by precedence: dependency is the hard constraint, value the soft preference among independent rungs. With the order fixed, the last property follows on its own — every prefix of the ladder runs.

Primary sources for ordering an increment plan by dependency and value, and where this connects in the course.