Algebra-Driven Design, Part 3: Generalisation, and Finding the Applicative

Following Chapter 2 of Algebra-Driven Design by Sandy Maguire (the algebra is originally Peter Henderson’s, from Functional Geometry, 1982). Part 2 designed an algebra for composing square tiles: rotations, mirrors, beside, above, quad, swirl, behind, and an observation rasterize. Still no implementation.

This post asks whether the design is overfit — whether it demands more than it needs. The answer is yes, and fixing it turns a picture library into something considerably stranger and more useful.

🔗The tell

Look at the constructors again and sort them into two piles.

Pile one — anything to do with colour: colour, behind, empty.

Pile two — everything else: cw, ccw, flipH, flipV, beside, above, quad, swirl.

Pile two moves things around in space. Not one of those eight operations cares what’s being moved. cw rotates a grid. It would rotate a grid of integers, characters, booleans, or functions with exactly as much enthusiasm as it rotates a grid of colours.

So the algebra is doing two separate jobs at once: managing space, and compositing colours. It’s only the second that needs pixels. Maguire’s rule of thumb applies — an overfit design carries constraints it doesn’t use — and the fix is to prise the two apart.

type Tile[A]

Now every signature changes:

// scala-check: skip
def cw[A](t: Tile[A]): Tile[A]
def ccw[A](t: Tile[A]): Tile[A]
def flipH[A](t: Tile[A]): Tile[A]
def flipV[A](t: Tile[A]): Tile[A]
def beside[A](l: Tile[A], r: Tile[A]): Tile[A]
def above[A](t: Tile[A], b: Tile[A]): Tile[A]
def quad[A](a: Tile[A], b: Tile[A], c: Tile[A], d: Tile[A]): Tile[A]
def swirl[A](t: Tile[A]): Tile[A]

def rasterize[A](w: Int, h: Int, t: Tile[A]): Vector[Vector[A]]

// still colour-specific, for now
def colour(r: Double, g: Double, b: Double, a: Double): Tile[Colour]
def behind(back: Tile[Colour], front: Tile[Colour]): Tile[Colour]
val empty: Tile[Colour]

Every law from part 2 survives unchanged. We didn’t weaken anything — we removed a constraint nobody was using.

And Tile is now a Functor. map changes every cell without touching the layout:

// scala-check: skip
given Functor[Tile] with
  def map[A, B](t: Tile[A])(f: A => B): Tile[B] = ???

Governed, as ever, by a law relating it to the observation:

rasterize(w, h, t.map(f)) = rasterize(w, h, t).map(_.map(f))

That equation is a functor homomorphism: mapping over a tile and then rasterizing is the same as rasterizing and then mapping over the pixels. Which is another way of saying map doesn’t secretly move anything around.

🔗Is it an Applicative?

Functor alone is thin gruel. The question worth asking is whether Tile is an Applicative — whether we can combine a tile of functions with a tile of values.

// scala-check: skip
def pure[A](a: A): Tile[A]
def ap[A, B](f: Tile[A => B])(a: Tile[A]): Tile[B]

pure is easy to guess: it’s colour generalised — fill the entire tile with one value.

ap is not obvious at all. What could it possibly mean to apply a tile of functions to a tile of values?

Here’s where the method earns its keep, because there’s a technique for exactly this situation: when the semantics of a constructor aren’t obvious, reason about the observation instead.

🔗Reasoning through the observation

rasterize has type (Int, Int, Tile[A]) => Vector[Vector[A]]. Shuffle the arguments:

Tile[A] => (Int, Int) => Vector[Vector[A]]

Under this reading, rasterize transforms a Tile[A] into a function (Int, Int) => Vector[Vector[A]]. So instead of asking “what does ap mean for tiles”, ask the concrete question: is there a sensible

// scala-check: skip
def f[A, B](
  ff: (Int, Int) => Vector[Vector[A => B]],
  fa: (Int, Int) => Vector[Vector[A]]
): (Int, Int) => Vector[Vector[B]]

that preserves our invariant — that the two integers are the width and height of the result?

The result is a nested Vector, so start with the applicative for Vector. And here’s the thing: there are two of them.

// scala-check: skip
// "substitute-y" — the cartesian product
List(inc, times8) <*> List(1, 5)   // List(2, 6, 8, 40)

// "zippy" — pointwise
zip(List(inc, times8), List(1, 5))  // List(2, 40)

Two inputs of length 2. The cartesian version gives length 4; the zippy version gives length 2. Only one of those preserves the width-and-height invariant. The cartesian applicative would produce a raster of the wrong size, which by our own specification means the wrong answer.

So the semantics of ap for tiles is: combine two tiles pixel by pixel. Not because it seemed nice, but because it’s the only option that survives the invariant. That’s the method working exactly as advertised — the design decision was forced, and we found the constraint that forced it before writing any code.

🔗The morphism, and the crack in the foundation

We can now state the law. Take a variant of rasterize that returns something with a zippy applicative — call the wrapper ZipGrid — and write:

rasterize'(w, h, ff.ap(fa)) = rasterize'(w, h, ff).ap(rasterize'(w, h, fa))

This is an applicative morphism. Maguire’s slogan for it, which he takes from Conal Elliott’s work on denotational design:

The instance’s observation follows the observation’s instance.

Read: to work out what an instance should do for your type, look at what the corresponding instance does for the type your observation produces. It’s a recipe, not a slogan, and it’s the single most reusable idea in the book.

Now — the crack. An Applicative is pure and ap. They come as a pair; they’re defined relative to each other. So if ap is a morphism, pure had better be one too:

rasterize'(w, h, pure(a)) =?= pure(a)

It isn’t. And you can see why the moment you try to write the zippy pure.

Zippy pure(a) has to be an identity for zipping. Zip anything of length n against it and get length n back. For a finite Vector, no such value exists — any fixed length k truncates every input longer than k. The only thing that works is an infinite sequence of a.

This isn’t a quirk of my encoding. It’s why Haskell’s ZipList is an Applicative (lazy lists can be infinite) and why, in cats, the zip-flavoured wrappers over strict collections get an Apply instance and not an Applicative. Apply is ap without pure — the typeclass hierarchy is shaped around exactly this hole, by people who hit it years before either of us did.

Two ecosystems, arrived at independently, agreeing that finite zip has no unit. That’s a strong signal.

Maguire’s diagnosis is blunt and correct:

A missing homomorphism means you chose the wrong observation.

pure wants to fill all of space with a value. rasterize can only produce a finite grid. The mismatch isn’t in pure — it’s in rasterize, which was never the right thing to reason about. We’ll fix it in part 5, and the fix is dramatic.

For now, note what just happened: an abstract algebraic argument about typeclass laws told us our architecture was wrong, before we wrote any code. That is not a thing I have previously experienced during API design.

🔗Monoids, hiding in plain sight

While we’re generalising, look again at empty and behind.

behind is associative — layering three tiles doesn’t depend on how you bracket them. And empty is its identity — a fully transparent layer changes nothing. Associativity plus identity is a monoid, and we already knew that from part 2 without using the word.

But behind’s associativity has nothing to do with tiles. It’s inherited wholesale from alpha compositing on colours, which is itself a monoid. So don’t hard-code it:

// scala-check: skip
def empty[A](using Monoid[A]): Tile[A]
def behind[A: Monoid](back: Tile[A], front: Tile[A]): Tile[A]

empty          = pure(Monoid[A].empty)
behind(b, f)   = map2(f, b)(_ |+| _)

Read that second law carefully. behind isn’t a primitive at all — it’s map2 over the monoid, with the arguments flipped so the front tile wins. The last two colour-specific operations in the algebra just became instances of something general.

Which leaves colour as the only colour-specific constructor, and even that is pure at a specific type. The colour-compositing half of the library has evaporated into a Monoid[Colour] instance, and the spatial half doesn’t know colours exist.

🔗What generality bought

Concretely — with Tile[A] polymorphic and an Applicative, here are things the original design could not express:

A tile of functions applied to a tile of values. Build beside(pure(identity), pure(invert)) — a tile whose left half is the identity function and whose right half inverts a colour — then ap it against a photo. Left half untouched, right half inverted. The layout algebra has become an image-processing language, and we added nothing to get there.

Non-colour tiles. Tile[Boolean] is a mask. Tile[Double] is a height field. Tile[Char] renders to a terminal. All of the spatial machinery applies unchanged.

Compositing modes, for free. The original design tempted us toward a behind variant for every blend mode — multiply, screen, overlay. Each would have been a half-baked idea welded into the algebra. With map2 you write the blend as an ordinary function and pass it in. One open-ended combinator beats fifteen closed ones, and Maguire lists this kind of orthogonality — no concept smeared across several constructors — as a marker of a good algebra.

If the higher-kinded machinery here is unfamiliar, the type lambdas and higher-kinded types post covers what Tile[_] as a type constructor actually means to the compiler, and the given/using post covers how the instances get found.

🔗Checking the laws with cats

Once part 4 gives us instances, we don’t hand-write applicative law tests. cats-laws and discipline already know them:

// scala-check: skip
import cats.laws.discipline.ApplicativeTests
import org.scalacheck.{Arbitrary, Cogen}

class TileLawTests extends munit.DisciplineSuite:
  checkAll("Tile.ApplicativeLaws", ApplicativeTests[Tile].applicative[Byte, Byte, Byte])
  checkAll("Tile.MonoidLaws", MonoidTests[Tile[List[Byte]]].monoid)

That’s associativity, identity, homomorphism, interchange, and composition, checked for free — provided we supply Arbitrary[Tile[A]] and an Eq[Tile[A]].

And Eq[Tile[A]] is where the whole series comes back around. It can’t be structural equality; it has to be observational — rasterize both at a range of sizes and compare. The definition of equality from part 2 is what makes the standard law suite usable at all.

Building those instances, and the generator, is part 4.

Next: Part 4 — The initial encoding, and generating a thousand tests.

---

🔗Sources

• Maguire, Sandy. Algebra-Driven Design. 2020. Chapter 2.4 (Generalization). https://leanpub.com/algebra-driven-design — the overfit diagnosis, the reason-through-the-observation technique, the cartesian-vs-zippy argument, and the missing-pure-homomorphism finding are all his.
• Elliott, Conal. Denotational design with type class morphisms. 2009 — the origin of “the instance’s observation follows the observation’s instance”, which Maguire quotes and builds on.
• Henderson, Peter. Functional Geometry. 1982 — the underlying tile algebra.
• cats (Typelevel) — Functor, Applicative, Apply, Monoid, and the cats-laws / discipline law suites used above.

The Scala 3 translation and the observation about cats’ Apply-not-Applicative treatment of zip wrappers are mine.