scala - 通用类型约束 ":<:"和 ":+:"在这个 Scala 示例中意味着什么？

Question

从 2017 年关于 nanopass 编译器的讨论 (https://github.com/sellout/recursion-scheme-talk/blob/master/nanopass-compiler-talk.org) 中，我找到了下面的代码片段。在这段代码片段中，我看到了两个通用约束，我搜索了高低以了解它们，但未能找到有关它们的任何信息。我希望了解的是:

• 这些运算符(operator)在做什么？
• 他们从哪里来？
• 最新版本的 Scala 和相关库中是否有更现代的等效项？

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

我很抱歉……我借用了一些 Haskell-y“类型运算符”来使内容更适合演讲的幻灯片，但我认为这只会造成更多困惑。

F :+: G会像 Coproduct[F, G, ?]其中 type Coproduct[F, G, A] = Either[F[A], G[A]] .也就是说，它允许您组合模式仿函数，用更小的片段构建更丰富的语言。

F :<: G有点复杂。它会像 Contains[F, G] , 其中

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

所以这段代码的一个更好的版本(虽然仍然无效——我已经有几年没写 Scala 了)

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
  }

我仍然使用这种技术，只是不在 Scala 中使用，我使用它的方式也发生了一些变化(例如，我将 expandLet 设为代数，以消除递归调用)。但至少该演讲中的概念仍然相关。

如果你想在 Scala 中编写这样的代码，我认为 Droste是这些天要走的路。