Scala type class syntax notes

notes.md

This page contains notes about a possible improvement to Scala for defining and working with type classes. It is mostly just notes at this point, not a proposal to be taken seriously.

Consider the following:

type class Functor[F[_]] {
  def map[A, B](fa: F[A], f: A => B): F[B]
  def replace[A, B](fa: F[A], replacement: => B): F[B] = map(fa, _ => replacement)
  def lift[A, B](f: A => B): F[A] => F[B] = fa => map(fa, f)
}

Note the type class syntax. We avoid the introduction of a new keyword and follow the pattern established by case class by letting type be a modifier for a class. Ignore the inability to repurpose the AST to support type class for a moment, which would require a language change. An annotation based approach could be used with a macro or compiler plugin (e.g., @typeclass abstract class Functor[F[_]] { ... }). Specifically, it is believed that macro annotations, provided by macro paradise, are sufficient to implement this proposal.

This results in:

• abstract class Functor
• object Functor with
  • generated implicit summoning apply method
  • generated synthetic class Adapter with methods generated for each Functor method that takes an F[A] as its first argument
  • generated adapt[A](a: A): Adapter[F, A] method on the Functor class, which instantiates an Adapter backed by the containing Functor
  • generated implicit wrapper method that instantiates a Adapter for an F[A]

Example of generated code:

trait Functor[F[_]] {
  def map[A, B](fa: F[A], f: A => B): F[B]
  def replace[A, B](fa: F[A], replacement: => B): F[B] = map(fa, _ => replacement)
  def lift[A, B](f: A => B): F[A] => F[B] = fa => map(fa, f)
  def adapt[A](fa: F[A]): Functor.Adapter[F, A] = new Functor.Adapter(fa)(this)
}

object Functor {
  def apply[F[_]](implicit F: Functor[F]): Functor[F] = F

  class Adapter[F[_], A](self: F[A])(implicit val functor: Functor) {
    def map[B](f: B): F[B] = functor.map(self, f)
    def replace[B](replacement: => B): F[B] = functor.replace(self, replacement)
  }
  implicit def Adapter[F[_]: Functor, A](self: F[A]): Adapter[F, A] = new Adapter(self)
}

Some things to note:

• both map and replace were included in the Adapter class because their first argument was an F[A]. As a result, the A type parameter was moved from the method signature to the class level.
• replace delegates to Functor.replace instead of inlining the implementation.
• lift was not added to the Adapter class because its first argument is not an F[A].
• adapt was added to the Functor class, which provides a non-implicit based way to use the functor operations in an OO style. This is useful for incoherent type classes. That is, when there are multiple, law abiding implementations of a type class for the same type, rather than selecting the adapter via implicit search, it can be selected by directly referencing the appropriate instance and calling adapt to get access to OO style operations.

Other general notes about such transformations:

• an Adapter class should not be generated if none of the type class methods take an X as their first argument, where X is shape compatible with the first type parameter to the type class
• Implemented as macro or compiler plugin, but proper support could make many optimizations

This transformation works for typeclasses that abstract over proper types as well. Consider:

type class Semigroup[A] {
  def append(x: A, y: A): A
}

This would generate:

trait Semigroup[A] {
  def append(x: A, y: A): A
  def adapt(x: A): Semigroup.Adapter[A] = new Semigroup.Adapter(x)(this)
}
  
object Semigroup {
  def apply[A](implicit S: Semigroup[A]): Semigroup[A] = S
  
  class Adapter[A](val self: A)(implicit val semigroup: Semigroup[A]) {
    def append(y: A): A = semigroup.op(self, y)
  }
  implicit def Adapter[A: Semigroup](x: A): Adapter[A] = new Adapter(x)
}

Subtyping is supported by making both the primary class and the adapter class extend the super type's corresponding types. For example:

type class Monoid[A] extends Semigroup[A] {
  def id: A
  def multiply(x: A, y: Int): A = ???
}

Produces:

trait Monoid[A] extends Semigroup[A] {
  def id: A
  def multiply(x: A, y: Int): A = ???
  override def adapt(a: A): Monoid.Adapter[A] = new Monoid.Adapter(a)(this)
}
object Monoid {
  def apply[A](implicit M: Monoid[A]): Monoid[A] = M
  class Adapter[A](self: A)(implicit val monoid: Monoid[A]) extends Semigroup.Adapter[A](self)(monoid) {
    def multiply(y: Int): A = monoid.multiply(self, y)
  }
  implicit def Adapter[A: Monoid](x: A): Adapter[A] = new Adapter(x)
}

In this case, the adapt method was overriden to return Monoid.Adapter[A] instead of Semigroup.Adapter[A]. Had Monoid not defined the multiply method, it would not have had an Adapter class generated, which would also result in neither an adapt override nor an Adapter implicit conversion.

In addition to the syntax extensions described so far, individual operations can be annotated with the op annotation, providing an operator alias for the operation. For example, the Semigroup trait could be written as:

type class Semigroup[A] {
  @op("|+|")
  def append(x: A, y: A): A
}

This causes an additional method to be generated, def |+|(y: A): A, on both the adapter, that forwards to the append method. In effect, this defines an operator alias for the method.

Finally, note that the adapter methods can be optimized to avoid allocations using the techniques employed by Machinist.