Attempt to create a higher-rank polymorphic function with type bounds

higher-rank polymorphic function with type bounds.scala

/*
  I want to use a higher-rank polymorphic function when transforming an AST to generalize the
  'traversal' so it can be separated from the actual transformation of each node. 
  
  This snippet of code doesn't quite capture my use case but it provokes the same compile error
  as I get here: https://gist.github.com/1139579
*/

trait ~>[F[_],G[_],C[_]] {
  def apply[A](a: F[A])(implicit evidence: C[F[A]]): G[A]
}

type Id[A] = A

// Just some data so I have something to use for my type bounds 
abstract class AClass[A] { def name(a: A): String; def setName(a: A, n: String): A }
case class BClass(name: String, age: Int)
case class CClass(name: String)

implicit val aClassB: AClass[BClass] = new AClass[BClass] {
  def name(b: BClass) = b.name
  def setName(b: BClass, s: String) = BClass(s, b.age)
}

implicit def aClassC: AClass[CClass] = new AClass[CClass] {
  def name(c: CClass) = c.name
  def setName(c: CClass, s: String) = CClass(s)
}

// Attempt to create higher-rank polymorphic function with type bounds on the input 
val transform = new (~>[Id,Id,AClass]) {
  def apply[A](a: A)(implicit ev: AClass[A]): A = ev.setName(a, ev.name(a).reverse)
}

def apply[B : AClass](f: ~>[Id,Id,AClass], b: B, c: CClass): (B, CClass) = (f(b), f(c))

println(apply(transform, new BClass("Mads", 21), new CClass("runarorama")))

I have stuff like this:

case class SJBinaryExpression (operation : String, left : SJExpression, right : SJExpression) extends SJExpression
case class SJFieldRead (value : SJVariableAccess, variable : SJVariableAccess, field : String) extends SJStatement

So in this case applying f: SJStatement => SJStatement to SJBinaryExpression.left or SJFieldRead.value will not yield a type that is restrictive enough for the compiler.

That's what got me to you blog post about rank-2 polymorphism because I thought that could solve the problem :)

Wait, how is that not restrictive enough? In an ADT, you should never talk about the constructors to the type system.

Here's the simplest example I can create to produce the compiler error:

type mismatch;
 found   : this.SJStatement
 required: this.SJExpression
    case SJConditional(test, c, a)     => f(SJConditional(f(test), map(c,f), map(a,f)))

/* Subset of our Simple Java AST */

sealed abstract class SJStatement
case class SJConditional (test : SJExpression, consequent : List[SJStatement], alternative : List[SJStatement]) extends SJStatement

trait SJExpression extends SJStatement
case class SJBinaryExpression (operation : String, left : SJExpression, right : SJExpression) extends SJExpression 
case class SJLiteral (value : String) extends SJExpression 

/* Map method */

def map(statements: List[SJStatement], f: SJStatement => SJStatement): List[SJStatement] = {
  statements map { _ match {
    case SJConditional(test, c, a)     => f(SJConditional(f(test), map(c,f), map(a,f)))
  }}
}