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")))

Okay, so this is very alien to me but I really want to understand how to use this and I believe it's the right way to solve my problem. What if instead of setting the name I want to set the name iff it's a CClass and name and age if it's a BClass? Would there be any way to bend the code to deal with this?

You could add methods to AClass, such as a setAge that for CClass just ignores it.

You could also use Either.

I see. In my case I have more than just two types (I have 12) and they all have distinct properties so adding x and setX methods for each property seems verbose.

I feel that my problem is fairly simple but no obvious solution has come to mind. I want to map over an Abstract Syntax Tree like you can map over a List with the purpose of separating the traversal code from the actual mapping. The AST is heterogeneous but with a common super-type (SJStatement) so I feel that it should be possible.

Sounds pretty straightforward. Why not just use a function (SJStatement => SJStatement) ?

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)))
  }}
}