Write the subtotal on every box

A text tree repeatedly scans subtrees to find character counts. Store a count at each node. A leaf measures its text length; an internal node combines child measurements with addition.

The carrier is the summary type, the operation combines adjacent summaries, and the identity measures an empty subtree. Associativity proves that any tree shape gives the same summary for the same leaf order. After an edit, rebuild measurements only along the path to the root.

Counts are one measurement. A text editor may combine length, line count, and the first or last newline position in a product summary. Each component still needs an honest associative operation. A property test compares cached measurement with a fresh fold after random edits.

Where the model stops

Metadata without a composition rule is merely cached state and may require a global repair. Associativity does not make an expensive summary cheap, and a monoid chapter should not conceal the memory cost of storing a value per node.

Lessons

• A measured structure caches a fold at each node.
• Identity handles emptiness; associativity permits tree regrouping.
• Local edits repair only the ancestor path.
• Commutativity and idempotence are separate laws.

Practice

1. Give an identity and combine operation for line counts.
2. Find a summary operation that is associative but order-sensitive.
3. Transfer measurement to priority maxima or bounding rectangles.

The next chapter asks what additional laws remove arrival order and duplication from merge.

References

1. “Ralf Hinze and Ross Paterson, “Finger Trees: A Simple General-purpose Data Structure”.” — monoidal measurements on persistent trees.