The Existential Unapply Trick

01.README.md

Did you ever run into the situation, where you thought you need higher ranked polymoprhism in Scala? While it is somewhat supported in Scala, once you go down this route, you loose some convenience that eventually disrupts your API. In this post, I show how in some cases we can use our old friend unapply in Scala to recover some of the convenience.

The Problem

Let's assume in your API you want to have users write functions of type:

trait F {
  def apply[X]: (... type uses X ...) => X
}

The user code then looks like:

val f: F = new F { def apply[X] = arg => ... }

Is there a way we can still use Scala's support for lambda-syntax? That is, can we somehow manage to write the following?

val f: F = { arg => ... }

The Restriction

Turns out, we can recover the concise notation if the following is true:

Our rank-2 interface F only mentions the type X in a contravariant position

That is, roughly, it has the form:

trait F {
  def apply[X]: (... type uses X ...) => ... type does not use X ...
}

The Solution

Now, if this restriction applies then we can rewrite our program as follows. First, we change the type of F to:

type F = FArg => ... type does not use X ...

then we define the new type FArg:

trait FArg
// library internal implementation detail:
private case class FArgImpl[X](arg: ... type uses X ...) extends FArg // here we hide the X

Now comes the trick, the only way to deconstruct a value of type FArg is by the following unapply method:

object F {
  def unapply[X](f: FArg): Option[... type uses X ...] = ...
}

This way our user programs becomes:

val f = { case F(arg) => ... }

An Application

Actually, I came up with this roundabout way of defining functions when rethinking the API of a freer effects library for Scala (similar to Atnos Eff).

The code for this shortened example can be found in a scastie.

The library roughly consists of the following types:

trait Op[R] { def unary_! : Eff[R] = ... }

sealed trait Eff[+A] {
  def map[B](f: A => B): Eff[B]
  def flatMap[B](f: A => Eff[B]): Eff[B]
}
def pure[A](a: => A): Eff[A]

Type Op is a marker trait for effect operations and Eff is the usual implementation of freer monads (but without effect safety!). A user program looks like:

case object Get extends Op[Int]
val prog = for {
  x <- !Get
  y <- !Get
} yield x + y

I wanted to define effect handlers (like for the operation Get) as partial functions. The first draft was

trait Handler[R] {
  def apply[X]: PartialFunction[Op[X], (X => Eff[R]) => Eff[R]]
}

which made user code a bit too clumsy for my taste:

def always42[R] = new Handler[R] {
  def apply[X] = {
    case Get => resume => resume(42)
  }
}

Applying the Trick™

We uncurry and first rewrite the Handler interface to

trait Handler[R] {
  def apply[X]: PartialFunction[(Op[X], X => Eff[R]], Eff[R]]
}

Now, we can apply the unapply trick from above, and rewrite Handler to:

type Handler[R] = PartialFunction[Operation[R], Eff[R]]

// Operation really just is `Eff` -- but we hide it from the user:
opaque type Operation[R] = Eff[R]
object Op {
  def unapply[R, X](o: Operation[R]): Option[(Op[X], X => Eff[R])] = ...
}

This way the type X which was universally quantified in Handler is brought into scope when pattern matching. We can now define handlers as:

def always42[R]: Handler[R] =  {
  case Op(Get, resume) => resume(42)
}

Much better, if you ask me :)

post.yml

layout: post
title: "The Existential Unapply Trick"
date: 2019-07-15 13:13
comments: false
categories:
- functional programming
- scala