It is impossible to pattern match on a case class containing partially applied type constructors

[scabug]

I have a feeling this is not easily fixable, but it looks like it is impossible to pattern match on a type that is parameterized on a type constructor, when that type constructor is instantiated to a type alias or some sort of type level function.

Here's an example, from a stream processing library I am working on:

trait Process[F[_,_], A]
case class Halt[F[_,_],A]() extends Process[F,A]
case class Emit[F[_,_],A](head: A, tail: Process[F,A]) extends Process[F,A]
case class Await[F[_,_],X,Y,A](fn: F[X,Y], arg: X, recv: Y => Process[F,A]) extends Process[F,A]

So, a Process can either halt, emit a value, or make an external request of its driver, where the external request is a call to evaluate the 'function' F. As a special case of this, we can constrain the requests to be of a particular type:

trait F1[A,B]
case class Get[B]() extends F1[Unit,B]

trait One[A] {
  type f[X,Y] = F1[Unit,A]
}

Now Process[One[Int]#f, String] is a stream transducer that can only request integer values from its sole input stream (and which emits Strings as its output type). The problem arises when I want to pattern match on a Process[One[A]#f, B]. I get 'constructor cannot be instantiated' errors:

object Failing {
  val a1 = Await[One[Int]#f,Unit,Int,String](Get[Int](), (), (i:Int) => Halt[One[Int]#f,String]())
  val x: Process[One[Int]#f,String] = a1
  val r = a1 match { case Await(f,x,r) => f }
}

This gives me:

<console>:32: error: constructor cannot be instantiated to expected type;
 found   : Await[F,X,Y,A]
 required: Await[[X, Y]F1[Unit,Int],Unit,Int,String]
         val r = a1 match { case Await(f,x,r) => f }
                                 ^
<console>:32: error: not found: value f
         val r = a1 match { case Await(f,x,r) => f }

I'm guessing this is just the usual limitation that a type constructor will never be inferred as a type level function, however it means that I can't meaningfully pattern match on Process, like if I want to implement piping the output of one process to another:

def pipe[A,B,C](p: Process[One[A]#f, B])(p2: Process[One[B]#f, C]): Process[One[A]#f, c] = ...

Is the only workaround here to define my own custom extractors?

[scabug]

Imported From: https://issues.scala-lang.org/browse/SI-6744?orig=1
Reporter: @pchiusano
Affected Versions: 2.9.2, 2.10.0-RC3
Duplicates #2712

[scabug]

@retronym said:
Things might work out better (at least, let you provide the type constructor explicitly) with something like:

trait Processes {
  type F[_, _]
  trait Process[A]
  case class Halt[A]() extends Process[A]
  case class Emit[A](head: A, tail: Process[A]) extends Process[A]
  case class Await[X,Y,A](fn: F[X,Y], arg: X, recv: Y => Process[A]) extends Process[A]
}

[scabug]

@retronym said:
Closing as a dup of #2712

[scabug]

@pchiusano said:
Cool. Sorry for the dup.

I don't think your workaround helps here, since now the Process types are completely unrelated to each other and can't be combined. :( One of the points of this library I am writing (it is based roughly on Ed's machines library and the port to Scala is that we can mix and match Processes with different capabilities (represented by their F argument).

The workaround I settled on was something like this:

case class Two[A,B]() { // a two input Process
  type f[x,y] { def get: Either[A =:= y, B =:= y] }
  case object L extends f[Unit,A] { def get = Left(implicitly) }
  case object R extends f[Unit,B] { def get = Right(implicitly) }
}

I then use Process[Two[A,B]#f,C] to represent a Process that accepts two inputs, and now f is an actual type, not just a type alias, so I can go back to pattern matching on Await. I can't pattern match on L and R (since TwoA,B.L != TwoA,B.L - they belong to completely separate types), but even if I could Scala is missing the GADT support that would refine the types properly there anyway. Instead I pattern match on the result of calling get, which contains an equality witness on either side that also lets me refine the types correctly. Somewhat annoying to use but not too horrible so far...