What do the generic type constraints ":<:" and ":+:" mean in this Scala example?

Question

From this talk about nanopass compilers in 2017 (https://github.com/sellout/recursion-scheme-talk/blob/master/nanopass-compiler-talk.org) I found the code snippet below. In this code snipped, I see two generic constraints that I have searched high and low to understand but have not been able to find any information about them. What I'm hoping to understand is:

• What are these operators doing?
• Where did they come from?
• Is there a more modern equivalent in the latest versions of Scala and related libraries?

final case class Let[A](bindings: List[(String, A)], body: A)
final case class If[A](test: A, consequent: A, alt: A)

def expandLet[Lambda :<: F]: Fix[Let :+: F] => Fix[F] =
  _.unFix match {
    case Let(bindings, body) =>
      bindings.unzip((names, exprs) =>
        Fix(App(Fix(Lam(names, expandLet(body)).inject),
                exprs.map(expandLet)).inject))
    // and don’t forget the other cases
  }

def expandIf[Lambda :<: F]: Fix[If :+: F] => Fix[F] =
  _.unFix match {
    case If(test, consequent, alt) =>
      Fix(App(expandIf(test), List(
        Fix(Lam(Nil, expandIf(consequent))),
        Fix(Lam(Nil, expandIf(alt))))))
    // seriously, still gotta handle the other cases
  }

Answer 1

My apologies … I borrowed some Haskell-y “type operators” to make things fit better on the slides for the talk, but I think it just caused more confusion.

F :+: G would be something like Coproduct[F, G, ?] where type Coproduct[F, G, A] = Either[F[A], G[A]]. I.e., it allows you to compose pattern functors, to build a richer language out of smaller pieces.

F :<: G is a bit more complicated. It would be something like Contains[F, G], where

trait Contains[F, G] {
  def inject[A](in: F[A]): G[A]
  def project[A](outOf: G[A]): Option[F[A]]
}

val theSame[F] = new Contains[F, F] {
    def inject[A](in: F[A]) = in
    def project[A](outOf: F[A]) = Some(outOf)
}

val onTheLeft[F, G] = new Contains[F, Coproduct[F, G]] {
    def inject[A](in: F[A]) = Left(in)
    def project[A](outOf: Coproduct[F, G]) = outOf match {
        case Left(in) => Some(in)
        case Right(_) => None
    }
}

val nested[F, G, H](implicit further: Contains[F, H]) =
    new Contains[F, Coproduct[G, H]] {
        def inject[A](in: F[A]) = Right(further.inject(in))
        def project[A](outOf: Coproduct[G, H]) = outOf match {
            case Left(_) => None
            case Right(h) => further.project(h)
        }
    }

So a better version of this code (although still not valid – I haven’t written Scala a few years) is

def expandLet[F](input: Fix[Coproduct[Let, F]])
                (implicit contains: Contains[Lambda, F])
    : Fix[F] =
  input.unFix match {
    case Left(Let(bindings, body)) =>
      bindings.unzip((names, exprs) =>
        Fix(App(Fix(Lam(names, expandLet(body)).inject),
                exprs.map(expandLet)).inject))
    // and don’t forget the other cases
  }

I still use this technique, just not in Scala, and they way I use it has changed a bit (e.g., I would make expandLet an algebra, to eliminate the recursive calls). But the concepts in that talk are still relevant, at least.

If you want to write code like this in Scala, I think Droste is the way to go these days.