Rank N Types in Scala 3

There is no Rank N Types in Scala 2, but you can use FunctionK from Cats to mimic Rank N Types.

This is a Rank 1:

// forall a b c. (b, c) -> (a -> a) -> (b, c)
def rank[A,B,C](a: (B, C), doSomething: A => A): (B, C) = (doSomething(a._1), doSomething(a._2))

It won't compile because `doSomething` is rank 1 in rank 2 place.

When compiler tried to figure our what type doSomething(a._1) really is, since =a._1: B fix the type doSomething: B => B so compiler knows that A = B, but latter on there is a doSomething(a._2) now compiler confused, A cannot be both B and C while there are no proof of B = C.

Simplest way to make Scala 2 is to use Cats FunctionK:

def rank[B,C](a: (B, C), doSomething: Id ~> Id): (B, C) = (doSomething(a._1), doSomething(a._2))

Note that the trick of FunctionK, which basically remove A from type parameter rank[A, B, C], which means compiler then has nothing to confuse about.

While it is not totally free to use cats, there are some boilerplate you have to do when defining doSomething:

def doSomething: Id ~> Id = new (Id ~> Id) {
  def apply[A](a: Id[A]): Id[A] = a
}

Type A is hidden in the apply method.

Now in Scala 3, you can simply do the same thing natively with Polymorphic function types.

// rank 2 type (forall a. a -> a)
val id = [A] => (a: A) => a

// forall b c. (b, c) -> (forall a. a -> a) -> (b, c)
def rank2[B,C](a: (B, C), doSomething: [A] => A => A): (B, C) = (doSomething(a._1), doSomething(a._2))

def main(args: Array[String]): Unit = {
  println(
    rank2((1, "2"), id)
  )
}

The trick is now A is defined [A] => A => A, no in method type parameters. It is quite similar to how we define rank n types in Haskell

forall b c. (b, c) -> (forall a. a -> a) -> (b, c)

So basically [A] => is the same thing as forall a.

Play around with the above examples in scatie: https://scastie.scala-lang.org/jcouyang/3hNle3faQ7SpS4mCcoMSGA/29

Or clone the repo and play locally: https://github.com/jcouyang/meow