Rohit's Blog

Following Chapter 9 of The Haskell School of Music by Paul Hudak. Parts 1, 2, and 3 built a music DSL, proved twelve laws about it, and gave it a proper performance model. All of that was about transcribing music that already existed.

This post generates some. It’s the shortest piece of code in the series and by a distance the most fun, and it’s the payoff for having made music a value rather than a side effect.

🔗The construction

Start with a short pattern — four notes, say. Now replace each note in the pattern with a copy of the whole pattern, transposed so it starts where that note was and squeezed into that note’s duration. You now have sixteen notes. Do it again for sixty-four.

That’s the entire idea. It’s the Sierpinski construction from the tile algebra with time as the axis instead of space, and — as with the tiles — the interesting thing is how little code expresses it.

A note in a pattern is a duration multiplier and a pitch offset, not an absolute note:

// scala-check: skip
type SNote = (Dur, AbsPitch)

(Rational(1,4), 7) means “a quarter of whatever duration I’m subdividing, seven semitones above whatever pitch I’m sitting on.” Relative, so it can be applied at any scale.

Combining two of them multiplies the durations and adds the offsets:

// scala-check: skip
def addMult(a: SNote, b: SNote): SNote =
  val ((d0, p0), (d1, p1)) = (a, b)
  (d0 * d1, p0 + p1)

Multiply-and-add. That’s the whole recursion, and it’s worth noticing it’s the same structure as the composition laws from part 2 — tempo is multiplicative, transposition is additive. The self-similar construction is what you get when you iterate the two modifier axioms against each other.

🔗An infinite tree, lazily

The tree has no bottom — every node has children forever. In Haskell that’s free. In Scala we reach for LazyList:

// scala-check: skip
final case class Cluster(note: SNote, children: LazyList[Cluster])

def selfSim(pat: List[SNote]): Cluster =
  def mk(n: SNote): Cluster =
    Cluster(n, LazyList.from(pat).map(p => mk(addMult(n, p))))
  Cluster((Rational(1), 0), LazyList.from(pat).map(mk))

Six lines for an infinitely deep tree. The recursion in mk calls itself unconditionally and still terminates, because LazyList.map doesn’t force its elements — mk is only invoked when someone actually looks at a child.

That’s a small but real difference from the Haskell. Hudak writes the same function with no laziness annotation because everything in Haskell is lazy by default; in Scala the laziness has to be chosen, and choosing wrong here is not a performance problem but a stack overflow. It’s the clearest case in the series of a place where the port needed a decision the original didn’t.

Then take a horizontal slice — every node at depth n:

// scala-check: skip
def fringe(n: Int, c: Cluster): List[SNote] =
  if n == 0 then List(c.note)
  else c.children.toList.flatMap(fringe(n - 1, _))

Depth n of a pattern with k notes gives you k^n notes. Four notes at depth 5 is 1024.

And render the slice as music, relative to a base pitch:

// scala-check: skip
def simToMusic(base: Pitch, notes: List[SNote]): Music[Pitch] =
  line(notes.map((d, p) => note(d, pitch(absPitch(base) + p))))

line is the foldRight over :+: from part 1. Everything downstream of here is machinery we already have.

🔗Why the durations should sum to one

Here’s the detail that makes the whole thing work, and it took me a while to see.

Durations multiply as you descend. So if your pattern’s durations sum to 1, then at every depth the total duration of the fringe is still exactly 1:

depth 1:  4 notes × 1/4              = 1
depth 2:  16 notes × 1/16            = 1
depth n:  4ⁿ notes × (1/4)ⁿ          = 1

Every level is the same length. The music gets exponentially denser and never gets longer.

Which is pleasant on its own, and it’s also what makes the next section possible: because depth 3 and depth 5 have identical total duration, you can play them simultaneously and they line up perfectly, with no padding and no arithmetic.

If the durations sum to something other than 1, each level is a different length and the harmony trick below silently falls apart. It’s the sort of invariant that would be worth a law if this were a library rather than a sketch.

🔗Making something

A pattern built from a major triad plus the octave, with the durations summing to one:

// scala-check: skip
val q = Rational(1, 4)

val triad: List[SNote] = List(
  (q, 0),    // root
  (q, 4),    // major third
  (q, 7),    // fifth
  (q, 12)    // octave
)

def piece(depth: Int): Music[Pitch] =
  simToMusic((PitchClass.C, 4), fringe(depth, selfSim(triad)))

And then just listen to the levels:

// scala-check: skip
@main def render(): Unit =
  for d <- 1 to 6 do
    writeMidi(tempo(Rational(1, 2), piece(d)), s"selfsim-$d.mid")

Depth 1 is the bare arpeggio. Depth 2 is an arpeggio of arpeggios and already sounds deliberate. By depth 4 it has the texture of a Bach prelude — the harmony moves at the slow level while the fast level fills in figuration, which is exactly how that music is constructed, and nobody told the program that.

Depth 6 is 4096 notes in the same wall-clock duration as depth 1, which is no longer music so much as timbre. That transition — where rhythm becomes fast enough to be heard as pitch and texture — happens somewhere around depth 5 or 6, and hearing it happen is worth the price of the whole series.

Two knobs worth turning:

Non-uniform durations. List((Rational(1,2), 0), (q, 4), (q, 7)) sums to 1 but is lopsided, so the subdivision is uneven and the result has a limp rather than a pulse. Much more musical than the uniform version.

Negative offsets. Any pitch offset can be negative; descending patterns fold back on themselves in a way ascending ones don’t.

🔗Self-similar harmony

Now the trick the sum-to-one property bought us. Play several depths at the same time:

// scala-check: skip
def harmony(base: Pitch, pat: List[SNote], depths: List[Int]): Music[Pitch] =
  chord(depths.map(d => simToMusic(base, fringe(d, selfSim(pat)))))

val piece = harmony((PitchClass.C, 4), triad, List(2, 3, 5))

Three lines. Every voice has the same total duration, so they align exactly — no padding, no rest. And they’re guaranteed to be harmonically consistent, because they’re the same structure at different resolutions: the slow voice is literally the harmonic skeleton the fast voice is decorating.

Assigning an instrument per depth is the obvious next move:

// scala-check: skip
def orchestrate(base: Pitch, pat: List[SNote], parts: List[(Int, Instr)]): Music[Pitch] =
  chord(parts.map { (d, inst) =>
    instrument(inst, simToMusic(base, fringe(d, selfSim(pat))))
  })

orchestrate((PitchClass.C, 4), triad,
  List(2 -> Instr.ChurchOrgan, 3 -> Instr.Vibraphone, 5 -> Instr.Flute))

Slow organ underneath, vibraphone in the middle, flute running the fast figuration. chord, instrument, and line are all from part 1. Nothing here knows what a fractal is.

🔗Cashing in part 2’s optimiser

Part 2 ended by building a normalise function out of the algebra’s laws, and I said honestly that it does nothing for hand-written music and that the real measurement belonged here. So:

Generated music is exactly the case it was built for. Each level of the construction wraps another Modify around the same subtree, and by depth 6 there are thousands of nested Tempo and Transpose nodes that the multiplicative and additive axioms collapse into one apiece.

The honest way to report this is to measure it — build the depth-6 orchestration, time perform before and after normalise, and quote the number. I’d expect the win to come mostly from Modify collapsing rather than from anything clever, and I’d expect it to be unimpressive below depth 4. I haven’t run it yet. When I do I’ll put the numbers here rather than an adjective; an optimiser you haven’t measured is a hypothesis.

What I can say without measuring is the part that isn’t about speed: every rewrite in normalise is one of Hudak’s axioms, so the transformed piece is provably the same music. Not “the tests still pass” — the same music, by the definition of equality we settled on in part 2. That guarantee is the thing the algebra bought, and it doesn’t depend on the benchmark going my way.

🔗What the series was actually about

Four posts, and the code that generates a five-minute piece of music is about thirty lines. That ratio is the argument.

The reason harmony is three lines isn’t that fractal music is easy. It’s that by the time we got here, line, chord, instrument, tempo, and :=: already existed, already composed, and were already known to obey laws that guarantee the composition means what it looks like it means. Part 4 is short because parts 1 to 3 did the work.

And the through-line I keep hitting in this whole strand of the blog shows up here too, in a smaller way than usual. Every argument in part 2 assumed referential transparency, and nothing in Scala enforced it — but the laziness in this post was different: LazyList made an infinite structure representable, and getting it wrong would have been a stack overflow at runtime rather than a silent wrong answer. Scala made me choose where Haskell chose for me, and in this one case I think being made to choose is better. It’s the only place in the series where the port improved on the original, and it’s worth ending on, because most of the time the traffic goes the other way.

🔗Sources

Hudak, Paul. The Haskell School of Music. Cambridge University Press. Chapter 9 (Self-Similar Music). The SNote representation, the Cluster tree, selfSim, fringe, the multiply-durations/add-pitches recursion, and the self-similar harmony idea are all Hudak’s. Euterpea: https://www.euterpea.com/
Maguire, Sandy. Algebra-Driven Design. 2020. https://leanpub.com/algebra-driven-design — for the Sierpinski construction this echoes, covered earlier in the tile series.

The Scala 3 translation, the LazyList encoding of the infinite tree, the observation about durations summing to one being what makes self-similar harmony align, and the specific patterns and orchestrations are mine.