Rohit's Blog

This series works through Paul Hudak’s The Haskell School of Music — a book that teaches functional programming by building a music language, then a synthesizer, then a reactive UI, in that order. Hudak’s library is Euterpea; this post ports its core to Scala 3. The design is his, the Scala is mine.

The algebra-driven design series was about designing libraries by writing equations first. This one is more direct: build something, make it make noise, then find out what you glossed over.

🔗Two ideas

Here is the whole insight the book is built on. There are exactly two ways to combine two pieces of music:

play one after the other
play them at the same time

That’s it. Everything else — melodies, chords, canons, orchestration — is those two operations applied recursively. It’s the same move as beside and above in the tile algebra, and I don’t think that’s a coincidence: both are algebras for filling a one- or two-dimensional space by subdividing it.

So the core type is an enum with four cases — a leaf, the two combinators, and a way to annotate:

// scala-check: skip
enum Primitive[+A]:
  case Note(d: Dur, a: A)
  case Rest(d: Dur)

enum Music[+A]:
  case Prim(p: Primitive[A])
  case Seq(m1: Music[A], m2: Music[A])      // one after the other
  case Par(m1: Music[A], m2: Music[A])      // at the same time
  case Modify(c: Control, m: Music[A])      // tempo, transposition, instrument

Dur is a duration as a fraction of a whole note — 1 is a whole note, 1/4 a quarter note, 1/3 a triplet. It has to be exact: the laws in part 2 depend on tempo(2) ∘ tempo(3) = tempo(6) holding on the nose, and floating point won’t give you that. I’m using spire’s Rational, which scala-cli makes a one-liner:

// scala-check: skip
//> using dep org.typelevel::spire:0.18.0
import spire.math.Rational

type Dur = Rational

🔗Why polymorphic?

Music[+A] rather than Music[Pitch]. Worth pausing on, because it’s the same generalisation move that made the tile algebra far more powerful than it looked.

None of Seq, Par, or Modify cares what’s in the notes. They arrange things in time. So the type parameter stays open, and you get:

Music[Pitch] — ordinary notes
Music[(Pitch, Volume)] — notes that know how loud they are
Music[(Pitch, List[NoteAttribute])] — what part 3 needs for real performance
Music[Unit] — pure rhythm, no pitch at all. A drum pattern.

The last one is my favourite. Rhythm is what you get when you throw away the pitch, and the type system says so.

🔗Pitches

enum PitchClass:
  case C, Cs, D, Ds, E, F, Fs, G, Gs, A, As, B

type Octave   = Int
type Pitch    = (PitchClass, Octave)
type AbsPitch = Int

def absPitch(p: Pitch): AbsPitch =
  val (pc, oct) = p
  12 * (oct + 1) + pc.ordinal

def pitch(ap: AbsPitch): Pitch =
  (PitchClass.fromOrdinal(ap % 12), ap / 12 - 1)

Middle C is (C, 4), which is absolute pitch 60 — the same number MIDI uses, which is not a coincidence and makes part of the next section free.

Hudak’s PitchClass carries the full enharmonic set — Cff, Cf, C, Cs, Css and so on for every letter, 35 constructors — because C-sharp and D-flat are the same key but not the same note, and notation software has to care. I’ve collapsed to the twelve chromatic pitches because nothing in this series notates anything. If you ever want to print a score, you want Hudak’s version.

🔗The operators, and a Scala gotcha worth knowing

Hudak writes sequential and parallel composition as :+: and :=:, which read beautifully:

c 4 qn :+: e 4 qn :+: g 4 qn        -- a melody
c 4 qn :=: e 4 qn :=: g 4 qn        -- a chord

Scala 3 lets us have exactly that, via extension methods with symbolic names. But there’s a trap, and it’s a good one:

In Scala, an operator whose name ends in : is right-associative, and the operands swap. a :: b is b.::(a). That’s why cons works the way it does.

Both of our operators end in :. So m1 :+: m2 does not call m1.:+:(m2) — it calls m2.:+:(m1). Write the extension the obvious way and every melody comes out backwards.

The fix is to name the parameters honestly and stop fighting it:

// scala-check: skip
extension [A](second: Music[A])
  def :+:(first: Music[A]): Music[A] = Music.Seq(first, second)
  def :=:(first: Music[A]): Music[A] = Music.Par(first, second)

Now a :+: b desugars to b.:+:(a), binds second = b, first = a, and builds Seq(a, b). Correct.

The right-associativity also means a :+: b :+: c parses as a :+: (b :+: c) rather than (a :+: b) :+: c. For music that’s harmless — part 2 proves both operations are associative, so the bracketing is unobservable. But it’s exactly the sort of thing that’s harmless until it isn’t, and it’s worth knowing why it’s harmless rather than being lucky.

🔗Constructors and durations

// scala-check: skip
def note(d: Dur, p: Pitch): Music[Pitch] = Music.Prim(Primitive.Note(d, p))
def rest(d: Dur): Music[Pitch]           = Music.Prim(Primitive.Rest(d))

val wn: Dur = Rational(1)      // whole note
val hn: Dur = Rational(1, 2)   // half
val qn: Dur = Rational(1, 4)   // quarter
val en: Dur = Rational(1, 8)   // eighth
val sn: Dur = Rational(1, 16)  // sixteenth

def c(o: Octave, d: Dur): Music[Pitch] = note(d, (PitchClass.C, o))
def d(o: Octave, dr: Dur): Music[Pitch] = note(dr, (PitchClass.D, o))
def e(o: Octave, d: Dur): Music[Pitch] = note(d, (PitchClass.E, o))
// ...and so on for the other nine

Twelve near-identical one-liners is not elegant, but it buys c(5, qn) at every call site for the rest of the series, and I’ll take that trade.

Then the modifiers:

// scala-check: skip
enum Control:
  case Tempo(r: Rational)
  case Transpose(i: AbsPitch)
  case Instrument(i: Instr)

def tempo[A](r: Rational, m: Music[A]): Music[A]     = Music.Modify(Control.Tempo(r), m)
def transpose[A](i: AbsPitch, m: Music[A]): Music[A] = Music.Modify(Control.Transpose(i), m)
def instrument[A](i: Instr, m: Music[A]): Music[A]   = Music.Modify(Control.Instrument(i), m)

Tempo(2) means twice as fast, so it divides durations. Which is backwards from what you’d guess, and is exactly the kind of thing that needs a law rather than a comment. Part 2.

🔗`line` and `chord`, or: why `fold` exists

Now the bit of the book I think is genuinely the best introduction to foldRight I’ve read.

You want to turn a list of notes into a melody. The obvious recursive definition:

// scala-check: skip
def line[A](ms: List[Music[A]]): Music[A] = ms match
  case Nil     => rest(0)
  case m :: ms => m :+: line(ms)

And a chord:

// scala-check: skip
def chord[A](ms: List[Music[A]]): Music[A] = ms match
  case Nil     => rest(0)
  case m :: ms => m :=: chord(ms)

Two functions, structurally identical, differing in one operator and nothing else. Hudak’s move is to abstract over exactly that difference — and what falls out is foldRight:

// scala-check: skip
def line[A](ms: List[Music[A]]): Music[A]  = ms.foldRight(rest(0))(_ :+: _)
def chord[A](ms: List[Music[A]]): Music[A] = ms.foldRight(rest(0))(_ :=: _)

I’ve seen foldRight motivated with sum and product a hundred times and it never landed. Motivated with “collapse a list of notes into a melody or a chord, same shape, different glue”, it lands immediately. The operator is the interesting parameter, and the music makes that visible in a way arithmetic doesn’t.

Two more we’ll need, both one-liners over what we have:

// scala-check: skip
def times[A](n: Int, m: Music[A]): Music[A] = line(List.fill(n)(m))
def offset[A](d: Dur, m: Music[Pitch]): Music[Pitch] = rest(d) :+: m

And duration, which is a fold of a different shape:

// scala-check: skip
def dur[A](m: Music[A]): Dur = m match
  case Prim(Note(d, _))        => d
  case Prim(Rest(d))           => d
  case Seq(m1, m2)             => dur(m1) + dur(m2)
  case Par(m1, m2)             => dur(m1) max dur(m2)
  case Modify(Control.Tempo(r), m) => dur(m) / r
  case Modify(_, m)            => dur(m)

Seq adds, Par takes the max — a parallel composition lasts as long as its longest voice. That asymmetry is the whole reason part 2’s duality law has a side condition.

🔗Making noise

The JVM ships a complete MIDI stack in javax.sound.midi, which almost nobody seems to know. No dependencies.

First, flatten a Music[Pitch] into timed events. This is a stripped-down version of what part 3 does properly:

// scala-check: skip
final case class Ev(onset: Dur, dur: Dur, pitch: AbsPitch, instr: Instr)

def events(m: Music[Pitch], t: Dur, c: Context): List[Ev] = m match
  case Prim(Note(d, p)) =>
    List(Ev(t, d / c.rate, absPitch(p) + c.shift, c.instr))
  case Prim(Rest(_)) =>
    Nil
  case Seq(m1, m2) =>
    events(m1, t, c) ++ events(m2, t + dur(m1) / c.rate, c)
  case Par(m1, m2) =>
    events(m1, t, c) ++ events(m2, t, c)
  case Modify(Control.Tempo(r), m)     => events(m, t, c.copy(rate = c.rate * r))
  case Modify(Control.Transpose(i), m) => events(m, t, c.copy(shift = c.shift + i))
  case Modify(Control.Instrument(i), m) => events(m, t, c.copy(instr = i))

Context carries the tempo rate, transposition, and instrument down the tree. It’s a Reader, and part 3 will say so.

This calls dur(m1) inside the Seq case, which walks the left subtree again — so events is quadratic in the depth of a right-leaning melody. Hudak flags exactly this and fixes it by having the traversal return the duration alongside the events. Part 3 does it properly. For a few hundred notes you will not notice.

Then build a Sequence:

// scala-check: skip
import javax.sound.midi.*

val PPQ = 96   // ticks per quarter note

def toSequence(evs: List[Ev]): Sequence =
  val seq   = Sequence(Sequence.PPQ, PPQ)
  val track = seq.createTrack()
  def tick(d: Dur): Long = (d * 4 * PPQ).toDouble.round   // 4 quarters per whole note

  for (ev, i) <- evs.zipWithIndex do
    val ch = i % 16
    track.add(MidiEvent(ShortMessage(ShortMessage.PROGRAM_CHANGE, ch, ev.instr.program, 0), 0))
    track.add(MidiEvent(ShortMessage(ShortMessage.NOTE_ON,  ch, ev.pitch, 100), tick(ev.onset)))
    track.add(MidiEvent(ShortMessage(ShortMessage.NOTE_OFF, ch, ev.pitch, 0),
                        tick(ev.onset + ev.dur)))
  seq

That channel allocation is wrong and I’m leaving it wrong on purpose — MIDI has 16 channels, each holding one instrument at a time, and channel 10 is reserved for percussion. Doing it properly means grouping events by instrument and assigning channels once. It’s a genuinely nice little constraint problem and it belongs in part 3.

Finally, output:

// scala-check: skip
def writeMidi(m: Music[Pitch], path: String): Unit =
  MidiSystem.write(toSequence(events(m, 0, Context.default)), 1, java.io.File(path))

def play(m: Music[Pitch]): Unit =
  val sequencer = MidiSystem.getSequencer
  sequencer.open()
  sequencer.setSequence(toSequence(events(m, 0, Context.default)))
  sequencer.start()

Reach for writeMidi first. Whether play produces audible sound depends on your JVM having a soundbank available, and that varies by JDK build and platform — on some you get a working synthesizer for free, on others getDefaultSoundbank returns null and you get silence with no error. A .mid file opens in anything and always works. If you want live playback and get nothing, that’s the soundbank, not your code.

🔗Frère Jacques, in four parts

The payoff. Here’s the melody, four two-bar phrases, each played twice:

// scala-check: skip
val p1 = line(List(c(5, qn), d(5, qn), e(5, qn), c(5, qn)))
val p2 = line(List(e(5, qn), f(5, qn), g(5, hn)))
val p3 = line(List(g(5, en), a(5, en), g(5, en), f(5, en), e(5, qn), c(5, qn)))
val p4 = line(List(c(5, qn), g(4, qn), c(5, hn)))

val frereJacques = line(List(p1, p1, p2, p2, p3, p3, p4, p4))

And a round is four copies of that, each delayed by two bars, each on a different instrument:

// scala-check: skip
def round(m: Music[Pitch], delay: Dur, instrs: List[Instr]): Music[Pitch] =
  chord(instrs.zipWithIndex.map { (inst, i) =>
    instrument(inst, offset(delay * i, m))
  })

val canon = round(
  frereJacques,
  delay  = wn * 2,
  instrs = List(Instr.Piano, Instr.Vibraphone, Instr.ChurchOrgan, Instr.Flute)
)

Five lines for a four-part canon. offset is rest(d) :+: m, round is a chord over lines, and neither knew anything about canons when we wrote them. That’s the argument for building the two combinators first and the vocabulary second.

🔗What’s not right yet

Deliberate gaps, each of which is a later post:

Playback is a hack. events is quadratic, channel allocation is broken, and there’s no notion of a performer — of how a phrase marked legato should actually sound, or how a pianist differs from a violinist. Part 3.

Nothing has been verified. tempo(2, tempo(3, m)) ought to equal tempo(6, m). Is that true of the code above? I believe so and I haven’t checked. Part 2, which turns twelve of those beliefs into property tests.

We’ve only transcribed music, not generated it. The interesting thing about having music as a value is that you can compute with it. Part 4 builds a piece by feeding a four-note pattern into itself recursively, and it sounds far better than it has any right to.

Next: Part 2 — An Algebra of Music, in which we ask what it means for two pieces of music to be equal, and get twelve laws and a monoid out of the answer.

🔗Sources

Hudak, Paul. The Haskell School of Music: From Signals to Symphonies. Cambridge University Press. Chapter 2 (Simple Music) and Chapter 3 (Polymorphic and Higher-Order Functions). The Music type, the :+: / :=: operators, line, chord, dur, and the use of music to motivate fold are all Hudak’s. Euterpea: https://www.euterpea.com/
The four-part round is Hudak’s exercise 3.12.
spire (Typelevel) for Rational; javax.sound.midi is part of the JDK.

The Scala 3 translation, the note on right-associative operator names, and the MIDI soundbank caveat are mine.