How to control the inferred type for bound variables in pattern matching in the presence of higher-kinded types

Question

(this is based on the article at http://bertails.org/2015/02/15/abstract-algebraic-data-type)

First, I am defining an abstract version of scala.Option.

import scala.language.higherKinds

trait OptionSig {
  type Option[+_]
  type Some[+A] <: Option[A]
  type None <: Option[Nothing]
}

abstract class OptionOps[Sig <: OptionSig] extends Extractors[Sig] {
  def some[A](x: A): Sig#Some[A]
  def none: Sig#None
  def fold[A, B](opt: Sig#Option[A])(ifNone: => B, ifSome: A => B): B
}

I want to be able to use pattern matching on Sig#Option[A] so Extractors looks like that:

trait Extractors[Sig <: OptionSig] { self: OptionOps[Sig] =>

  object Some {
    def unapply[A](opt: Sig#Option[A]): scala.Option[A] =
      fold(opt)(scala.None, a => scala.Some(a))
  }

  object None {
    def unapply[A](opt: Sig#Option[A]): Option[Unit] =
      fold(opt)(scala.Some(()), _ => scala.None)
  }

}

Now I can write this program:

class Program[Sig <: OptionSig](implicit ops: OptionOps[Sig]) extends App {

  import ops._

  val opt: Sig#Option[Int] = some(42)

  opt match {
    case None(_)  => sys.error("")
    case Some(42) => println("yay")
    case Some(_)  => sys.error("")
  }

}

And I can test it with this implementation.

trait ScalaOption extends OptionSig {

  type Option[+A] = scala.Option[A]
  type Some[+A]   = scala.Some[A]
  type None       = scala.None.type

}

object ScalaOption {

  implicit object ops extends OptionOps[ScalaOption] {

    def some[A](x: A): ScalaOption#Some[A] = scala.Some(x)

    val none: ScalaOption#None = scala.None

    def fold[A, B](opt: ScalaOption#Option[A])(ifNone: => B, ifSome: A => B): B =
      opt match {
        case scala.None    => ifNone
        case scala.Some(x) => ifSome(x)
      }

  }

}

object Main extends Program[ScalaOption]

It looks like it works but there is one annoying thing I cannot figure out.

With, scala.Option, the type of s in Option(42) match { case s @ Some(42) => s } is Some[Int]. But with my snippet above, it is Sig#Option[Int] and I would like to make it Sig#Some[Int] instead.

So I tried the following to be closer to what scalac generates for its case classes:

trait Extractors[Sig <: OptionSig] { self: OptionOps[Sig] =>

  object Some {
    def unapply[A](s: Sig#Some[A]): scala.Option[A] =
      fold(s)(scala.None, a => scala.Some(a))
  }

  object None {
    def unapply(n: Sig#None): Option[Unit] =
      fold(n)(scala.Some(()), (_: Any) => scala.None)
  }

}

But now I get warnings like the following:

[warn] Main.scala:78: abstract type pattern Sig#None is unchecked since it is eliminated by erasure
[warn]     case None(_)  => sys.error("")

I am not sure why this is happening as Sig#None is a subtype of Sig#Option[Int] and this is known at compile time.

Also the runtime is still ok, but the inferred type is still not the one I was expecting.

So the questions are

• why is type erasure mentioned here despite the subtyping information?
• how to get Sig#Option[Int] for s in (some(42): Sig#Option[Int]) match { case s @ Some(42) => s }

Answer 1

Unfortunately, you cannot do what you want. The problem is that it is not enough that scalac know that Sig#None <: Sig#Option[A], it must be able to verify that the value it is passing to unapply is, in fact, Sig#None. This works for scala.Option, because the compiler can generate an instanceof check to verify that a type is actually a Some or a None before passing it to the unapply method. If it fails the check, it skips that pattern (and unapply is never called).

In your case, since scalac only knows that opt is a Sig#Option[Int], it cannot do anything to guarantee that the value is actually a Some or None before passing it along to unapply.

So what does it do? It passes the value along anyways! What does this mean? Well, let's modify your extractors a bit:

trait Extractors[Sig <: OptionSig] { self: OptionOps[Sig] =>
  object Some {
    def unapply[A](s: Sig#Some[A]): scala.Option[A] =
      fold(s)(scala.None, a => scala.Some(a))
  }

  object None {
    def unapply(n: Sig#None): Option[Unit] =
      scala.Some(())
  }
}

All we've done is stopped using fold in the None case. Since we know the argument must be a Sig#None, why even bother calling fold, right? I mean, we wouldn't expect a Sig#Some to be passed here, right?

When we run this example, you'll hit a RuntimeException, because our very first pattern match succeeds and calls ???. In the case of scala.Option, the pattern would fail because it's guarded by a generated instanceof check.

I've gisted another example that shows another danger, where we add a small constraint to Sig#Some, which let's us avoid the fold in the Some case too: https://gist.github.com/tixxit/ab99b741d3f5d2668b91

Anyways, your specific case is technically safe. We know that you used fold and so it is safe to use with an Sig#Option. The problem is that scalac doesn't know that.