scala - 如何使用匹配类型实现 SKI 组合子演算？

Question

我正在尝试实现 SKI combinator calculus在 Dotty 中使用匹配类型。

SKI 组合子演算的简要说明:

• S、K 和I 是词条
• (xy) 是一个术语，如果 x 和 y 是术语，就像函数应用
• (((Sx)y)z)(与Sxyz相同)返回xz(yz)(与相同( xz)(yz))
• ((Kx)y)(与 Kxy 相同)返回 x
• (Ix) 返回 x

下面是我使用的(R 尽可能减少术语)。术语(xy)被写成一个元组(x,y)，以及S、K和I 是特征。

trait S
trait K
trait I

type R[T] = T match {
  case (((S,x),y),z) => R[((x,z),(y,z))]
  case ((K,x),y) => R[x]
  case (I,x) => R[x]
  case (a,b) => R[a] match {
    case `a` => (a, R[b])
    case _ => R[(R[a], R[b])]
  }
  case T => T
}

但是，以下两行无法编译(出于相同的原因)(Scastie):

val check: (K, K) = ??? : R[(((S,I),I),K)]
val check2: (K, K) = ??? : R[((I,K),(I,K))]

错误表明它需要 (K,K) 但找到了 R[((I, K), (I, K))]。我希望它首先看到 S 并将其转换为 (IK)(IK)，或 R[((I,K),(I,K))]，之后它应该匹配第一个 (I, K) 的评估并看到它是 K，这与 (I, K) 不同，使其返回 R[(R[(I,K)], R[(I,K)])]，它变成 R[(K,K) ]，它变成了 (K,K)。

但是，它不会超出 R[((I,K),(I,K))]。显然，如果它是嵌套的，它不会减少术语。这很奇怪，因为我尝试了相同的方法，但使用了实际的运行时函数，而且它似乎可以正常工作 ( Scastie)。

case object S
case object K
case object I

def r(t: Any): Any = t match {
  case (((S,x),y),z) => r(((x,z),(y,z)))
  case ((K,x),y) => r(x)
  case (I,x) => r(x)
  case (a,b) => r(a) match {
    case `a` => (a, r(b))
    case c => (c, r(b))
  }
  case _ => t
}

println(r((((S, I), I), K))) 的输出是 (K,K)，正如预期的那样。

有趣的是，删除 K 的规则使其可以编译，但它无法识别 (K, K) 和 R[(K, K )] 作为同一类型。也许这就是导致问题的原因？ ( Scastie )

def check2: (K, K) = ??? : R[(K, K)]
//Found:    R[(K, K)]
//Required: (K, K)

Answer 1

S、K 和 I 不相交。 K 与 I 等交叉路口有人居住:

println(new K with I)

在匹配类型中，只有当类型不相交时才会跳过大小写。所以，例如这失败了:

type IsK[T] = T match {
  case K => true 
  case _ => false
}
@main def main() = println(valueOf[IsK[I]])

因为不能跳过 case K => _ 分支，因为 I 的值是 K s。所以，例如在你的例子中 R[(K, K)] 卡在了 case (I, x) => _ 上，因为有 一些 (K, K) 也是 (I, x)(例如 (new K with I, new K {}))。您永远不会到达 case (a,b) => _，这会将我们带到 (K, K)。

您可以创建 S、K 和 I class，这使它们不相交，因为您不能同时继承两个 class。

class S
class K
class I

type R[T] = T match {
  case (((S,x),y),z) => R[((x,z),(y,z))]
  case ((K,x),y) => R[x]
  case (I,x) => R[x]
  case (a,b) => R[a] match {
    case `a` => (a, R[b])
    case _ => R[(R[a], R[b])]
  }
  case T => T
}

@main def main(): Unit = {
  println(implicitly[R[(K, K)] =:= (K, K)])
  println(implicitly[R[(((S,I),I),K)] =:= (K, K)])
}

Scastie

另一种解决方案是让它们都成为单例类型:

object S; type S = S.type
object K; type K = K.type
object I; type I = I.type
// or, heck
type S = 0
type K = 1
type I = 2