polykindrecursion.scala

object Test {
  abstract class Recursive[T <: AnyKind] {
    type Base[_ <: AnyKind] <: AnyKind

    type ~~>[_ <: AnyKind, _ <: AnyKind]

    def project: T ~~> Base[T]
  }

  object Recursive {
    type Aux[T <: AnyKind, F[_ <: AnyKind] <: AnyKind, Arr[_ <: AnyKind, _ <: AnyKind]] =
      Recursive[T] {
        type Base[A <: AnyKind] = F[A]
        type ~~>[_ <: AnyKind, _ <: AnyKind]
      }
  }

  trait ~>[F[_], G[_]] {
    def apply[A](fa: F[A]): G[A]
  }

  // single-sorted recursion

  final case class Fix[F[_]](unFix: F[Fix[F]])

  object Fix {
    implicit def recursive[F[_]]: Recursive.Aux[Fix[F], F, Function1] =
      new Recursive[Fix[F]] {
        type Base[A] = F[A]

        type ~~>[A, B] = A => B

        def project: Fix[F] => F[Fix[F]] = _.unFix
      }
  }

  // multi-sorted recursion (comments have kind-projected version)

  //    case class FixH[F[_[_], _], A](hunFix: F[FixH[F, ?], A])
  final case class FixH[F[_[_], _], A](hunFix: F[({ type λ[α] = FixH[F, α] })#λ, A])

  object FixH {
    //       def recursive[F[_[_], _]]: Recursive.Aux[FixH[F, ?], F, ~>] =
    implicit def recursive[F[_[_], _]]: Recursive.Aux[({ type λ[α] = FixH[F, α] })#λ, F, ~>] =
      //  Recursive[FixH[F, ?]] {
      new Recursive[({ type λ[α] = FixH[F, α] })#λ] {
        type Base[A[_], I] = F[A, I]

        type ~~>[A[_], B[_]] = A ~> B

        // def project: FixH[F, ?] ~> F[FixH[F, ?], ?] =
        //   new (FixH[F, ?] ~> F[FixH[F, ?], ?]) {
        //     def apply[A](fa: FixH[F, A]): F[FixH[F, α], A] = fa.hunFix
        def project: ({ type λ[α] = FixH[F, α] })#λ ~> ({type λ[α] = F[({ type λ[α] = FixH[F, α] })#λ, α] })#λ =
          new (({ type λ[α] = FixH[F, α] })#λ ~> ({type λ[α] = F[({ type λ[α] = FixH[F, α] })#λ, α] })#λ) {
            def apply[A](fa: FixH[F, A]): F[({ type λ[α] = FixH[F, α] })#λ, A] = fa.hunFix
          }
      }
  }
}

Currently gives me this error:

polykindrecursion.scala:21: error: type mismatch;
 found   : Test.Recursive[Test.Fix[F]]{type Base[A(in type Base)] = F[A(in type Base)]; type ~~>[A(in type ~~>), B] = A(in type ~~>) => B; def project: Test.Fix[F] => F[Test.Fix[F]]}
 required: Test.Recursive.Aux[Test.Fix[F],F,Function1]
    (which expands to)  Test.Recursive[Test.Fix[F]]{type Base[A <: AnyKind] = F[A]; type ~~>[A <: AnyKind, B <: AnyKind] = A => B}
      new Recursive[Fix[F]] {
      ^
one error found

Errors with revision 2:

polykindrecursion.scala:28: error: type mismatch;
 found   : Test.Recursive[Test.Fix[F]]{type Base[A(in type Base)] = F[A(in type Base)]; type ~~>[A(in type ~~>), B] = A(in type ~~>) => B; def project: Test.Fix[F] => F[Test.Fix[F]]}
 required: Test.Recursive.Aux[Test.Fix[F],F,Function1]
    (which expands to)  Test.Recursive[Test.Fix[F]]{type Base[A <: AnyKind] = F[A]; type ~~>[_ <: AnyKind, _ <: AnyKind]}
      new Recursive[Fix[F]] {
      ^
polykindrecursion.scala:44: error: type λ takes type parameters
    implicit def recursive[F[_[_], _]]: Recursive.Aux[({ type λ[α] = FixH[F, α] })#λ, F, ~>] =
                                                                                   ^
polykindrecursion.scala:44: error: F takes two type parameters, expected: one
    implicit def recursive[F[_[_], _]]: Recursive.Aux[({ type λ[α] = FixH[F, α] })#λ, F, ~>] =
                                                                                      ^
polykindrecursion.scala:46: error: type λ takes type parameters
      new Recursive[({ type λ[α] = FixH[F, α] })#λ] {
                                                 ^
four errors found

Here is my compiling version that does what it does but don't ask me what ;););)

object Test {
  abstract class Recursive[T <: AnyKind, Base <: AnyKind, ~~>[_ <: AnyKind, _ <: AnyKind]] {
    def project: T ~~> Base
  }

  object Recursive {
    type Aux[T <: AnyKind, Base <: AnyKind, ~~>[_ <: AnyKind, _ <: AnyKind]] = Recursive[T, Base, ~~>]
  }

  trait ~>[F[_], G[_]] {
    def apply[A](fa: F[A]): G[A]
  }

  // single-sorted recursion
  final case class Fix[F[_]](unFix: F[Fix[F]])

  object Fix {
    implicit def recursive[F[_]]: Recursive.Aux[Fix[F], F[Fix[F]], Function1] =
      new Recursive[Fix[F], F[Fix[F]], Function1] {
        def project: Fix[F] => F[Fix[F]] = _.unFix
      }
  }

  // multi-sorted recursion (comments have kind-projected version)
  final case class FixH[F[_[_], _], A](hunFix: F[({ type λ[α] = FixH[F, α] })#λ, A])

  object FixH {
    //       def recursive[F[_[_], _]]: Recursive.Aux[FixH[F, ?], F, ~>] =
    implicit def recursive[F[_[_], _]]: Recursive.Aux[
      ({ type λ[α] = FixH[F, α] })#λ
    , ({type λ[α] = F[({ type λ[α] = FixH[F, α] })#λ, α] })#λ
    , ~>] = {

      type In[A] = FixH[F, A]
      type Out[A] = F[In, A]

      new Recursive[In, Out, ~>] {
        def project: In ~> Out = new (In ~> Out) {
          def apply[A](fa: In[A]): Out[A] = fa.hunFix
        }
      }
    }
  }

}