BAM Weblog

Constraints are for methods, not data

Brian McKenna2017-11-22

I wrote this post a couple of years ago for a team at work. I just found it again, so here it is:

We gain two things by making a type more polymorphic:

  1. We can use it in more places
  2. We can reason about what it can't do, often to the point that we can count that there's only X possible implementations of a type signature (a topic called parametricity, covered pretty well elsewhere)

We should strive to be as polymorphic as possible to get the maximum advantages. I see a common mistake in Scala code where we put constraints in the wrong places, artificially limiting our benefits.

We have a PrefixTree data type in our code. It used to be encoded as a class like:

sealed abstract class PrefixTree[A: Prefix] {
  def add(a: A): PrefixTree[A]
}

case class Node[A: Prefix](prefix: A, child: PrefixTree[A]) extends PrefixTree[A]
case class Children[A: Prefix](suffixes: Vector[PrefixTree[A]]) extends PrefixTree[A]
case class End[A: Prefix]() extends PrefixTree[A]
case class Empty[A: Prefix]() extends PrefixTree[A]

Each of the constructors of a PrefixTree took evidence of being able to calculate a prefix for a type. Adding an element would then look at the evidence we got at construction time.

Now, what if we wanted to add an isEmpty method? Ideally the type signature would not mention Prefix, since we don't need to talk about any elements in the tree to check whether the tree is empty. Sadly the type of PrefixTree already mentions Prefix, so we've failed - the implementation could start using the methods on Prefix and return a Boolean which depended upon the elements within the tree. We've not obtained the 2nd goal I put above.

Instead, we should encode the data type slightly differently:

sealed trait PrefixTree[A] {
  def add(a: A)(implicit P: Prefix[A]): PrefixTree[A]
}

case class Node[A](prefix: A, child: PrefixTree[A]) extends PrefixTree[A]
case class Children[A](suffixes: Vector[PrefixTree[A]]) extends PrefixTree[A]
case class End[A]() extends PrefixTree[A]
case class Empty[A]() extends PrefixTree[A]

The only change is taking the Prefix constraints away from the constructors and moving it up to the method. Now if we wanted to add an isEmpty method without talking about Prefix, we can!

I've done this for a things in our codebase and we're a lot better of for it, both in benefits to reasoning but also reuse.

The method takes a bit of practice in Scala but please remember some simple advice: constraints belong on methods, not on data.

Please enable JavaScript to view the comments powered by Disqus.