在此 Scala 示例中，泛型类型约束“:<:”和“:+:”意味着什么？

Question

从 2017 年有关 nanopass 编译器的演讲 ( https://github.com/sellout/recursion-scheme-talk/blob/master/nanopass-compiler-talk.org ) 中，我找到了下面的代码片段。在这段代码片段中，我看到两个通用约束，我已经上下搜索以理解它们，但无法找到有关它们的任何信息。我希望了解的是：

\n

\n
• 这些运营商在做什么？
\n
• 哪儿来的呢？
\n
• 最新版本的 Scala 和相关库中是否有更现代的等效项？
\n

\n

final case class Let[A](bindings: List[(String, A)], body: A)\nfinal case class If[A](test: A, consequent: A, alt: A)\n\ndef expandLet[Lambda :<: F]: Fix[Let :+: F] => Fix[F] =\n  _.unFix match {\n    case Let(bindings, body) =>\n      bindings.unzip((names, exprs) =>\n        Fix(App(Fix(Lam(names, expandLet(body)).inject),\n                exprs.map(expandLet)).inject))\n    // and don\xe2\x80\x99t forget the other cases\n  }\n\ndef expandIf[Lambda :<: F]: Fix[If :+: F] => Fix[F] =\n  _.unFix match {\n    case If(test, consequent, alt) =>\n      Fix(App(expandIf(test), List(\n        Fix(Lam(Nil, expandIf(consequent))),\n        Fix(Lam(Nil, expandIf(alt))))))\n    // seriously, still gotta handle the other cases\n  }\n

\n

Answer 1

抱歉 \xe2\x80\xa6 我借用了一些 Haskell-y \xe2\x80\x9ctype 运算符\xe2\x80\x9d 以使内容更适合演讲的幻灯片，但我认为这只会引起更多混乱。

\n

F :+: G会是类似Coproduct[F, G, ?]where 的东西type Coproduct[F, G, A] = Either[F[A], G[A]]。即，它允许您编写模式函子，用较小的片段构建更丰富的语言。

\n

F :<: G有点复杂。会是这样的Contains[F, G]，在哪里

\n

trait Contains[F, G] {\n  def inject[A](in: F[A]): G[A]\n  def project[A](outOf: G[A]): Option[F[A]]\n}\n\nval theSame[F] = new Contains[F, F] {\n    def inject[A](in: F[A]) = in\n    def project[A](outOf: F[A]) = Some(outOf)\n}\n\nval onTheLeft[F, G] = new Contains[F, Coproduct[F, G]] {\n    def inject[A](in: F[A]) = Left(in)\n    def project[A](outOf: Coproduct[F, G]) = outOf match {\n        case Left(in) => Some(in)\n        case Right(_) => None\n    }\n}\n\nval nested[F, G, H](implicit further: Contains[F, H]) =\n    new Contains[F, Coproduct[G, H]] {\n        def inject[A](in: F[A]) = Right(further.inject(in))\n        def project[A](outOf: Coproduct[G, H]) = outOf match {\n            case Left(_) => None\n            case Right(h) => further.project(h)\n        }\n    }\n

\n

所以这个代码的更好版本（尽管仍然无效 \xe2\x80\x93 我已经\xe2\x80\x99t 写过 Scala 几年了）是

\n

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

\n

我仍然使用这种技术，只是不在 Scala 中使用，而且我使用它的方式已经改变了一点（例如，我会做expandLet一个代数，以消除递归调用）。但至少那次演讲中的概念仍然相关。

\n

如果你想在 Scala 中编写这样的代码，我认为Droste是目前的最佳选择。

\n