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

Question

我试图使用匹配类型在 Dotty 中实现SKI 组合器演算。

SKI 组合子演算的快速描述：

• S, K, 和I是项
• (xy)是一个术语 ifx并且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)]、变成 just 不同(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)。

有趣的是，删除规则 forK让它编译，但它不能识别(K, K)和R[(K, K)]作为相同的类型。也许这就是导致问题的原因？（斯卡斯蒂）

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

Answer 1

S、K、 和I不相交。十字路口K with 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秒。因此，例如，在你的情况下R[(K, K)]被卡住的case (I, x) => _，因为有一些(K, K)S中的也是(I, x)S（例如(new K with I, new K {})）。你永远不会到达case (a,b) => _，这会带我们去(K, K)。

您可以使S、K和I classes 不相交，因为您不能同时从两个classes继承。

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

斯卡斯蒂

另一种解决方案是使它们全部为单例类型：

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