与 HKT 的模式匹配 - 避免强制转换 return 类型

Question

在下面的示例中，虽然模式匹配在技术上是正确的，但显然转换是错误的。我可以在不必使用 asInstanceOf 的情况下重新表述吗？ IE。改变pattern match的写法或调整Transform.

的界面

trait Pat[A] {
  def transform(t: Transform): Pat[A] = ???
  def expandList: List[A]
}

trait Transform {
  def apply[X](in: Pat[X]): Pat[X]
}

case class FoldLeft[B, A](outer: Pat[Pat[B]], z: Pat[A], itIn: Pat[B], 
                          itCarry: Pat[A], inner: Pat[A]) extends Pat[A] {
  def expandList: List[A] = ???

  def test(): Unit = {
    val outerList: List[Pat[B]] = outer.expandList
    outerList.foldLeft(z) { (y: Pat[A], x: Pat[B]) =>
      val t = new Transform {
        def apply[X](in: Pat[X]): Pat[X] = in match {
          case `itIn`     => x.asInstanceOf[Pat[X]]  // ugly cast
          case `itCarry`  => y.asInstanceOf[Pat[X]]  // ugly cast
          case other      => other
        }
      }
      t[A](inner).transform(t)
    }
  }
}

如果您想知道 FoldLeft 的含义是什么，这里有一些例子：

Pat(Pat(1), Pat(2), Pat(3)).foldLeft(0) { (y, x) => y + x }

（你明白了；Pat 就像一个 Stream 描述符 ，所以我正在捕获这个过程的 AST，即为了执行左折，我正在创建一个代表该过程的 FoldLeft，其中 Pat(1, 2, 3) 变为 outer，0 变为 z，闭包是"evaluated" 具有虚拟模式 itIn (x) 和 itCarry (y)，生成闭包的模式版本，inner:

FoldLeft(Pat(Pat(1), Pat(2), Pat(3)), Pat(0), It("a"), It("b"),
  BinaryOp(Plus, It("b"), It("a")))  // similar to this

Answer 1

如果您被迫在所有类型都摆在您面前的代码中使用 asInstanceOf，那么这通常意味着代码中的某些抽象保证了它无法在其类型签名中实现的某些内容。您的代码中有几个地方看起来很可疑：

Pat[A]-trait 试图跟踪类型，但在下一行 inner foldLeft 二元操作的主体 没有说明它包含的孔的类型。现在是哪一个，是类型安全，还是 (Any, Any) => A 的 AST 带有类型 Any?
Transform 附带一个签名方法 apply[X](x: Pat[X]): Pat[X]，它本质上说："I am a natural transformation, I will treat all X equally!"，但是当你第一次实例化它时，你对待有些 A 和 B 不同。

asInstanceOf 悄悄进入您的代码，因为它试图维持这样一种错觉，即这两个抽象 Par 和 Transform 做他们在签名中假装做的事情。

要摆脱 asInstanceOf，您必须以 non-closed 的形式跟踪变量的类型。这可以通过以下方式实现：

使用Par[A]表示仅封闭类型A
为表达式创建一个单独的特征 Par2[V1, V2, A] V1 和 V2
而不是假装平等对待每个 Par[X] 的 Transform，创建一个 Graft2[V1, V2] 特征，在其签名中明确说明它只能填充类型 [=30] 的空洞=] 和 V2.
让Var2_1和Var2_2（Par2的子类）对Graft2

然后你可能会得到这样的东西（编译，工作，没有asInstanceOf）：

/** A pattern that represents closed expressions
  * that evaluate to something of type `X`.
  */
sealed trait Pat[X]
case class IntPat(i: Int) extends Pat[Int]

case class BinopPat[A, B, C](
  a: Pat[A], 
  b: Pat[B], 
  op: (A, B) => C
) extends Pat[C]

case class FoldLeft[A, B](
  bs: List[Pat[B]], 
  z: Pat[A], 
  op: PatFunc2[A, B, A]
) extends Pat[A] {
  /** Symbolically executes the `foldLeft`-operation */
  def eval: Pat[A] = bs.foldLeft(z)(op.graft)
}

/** Symbolic function with two arguments of 
  * type `V1` and `V2` that returns values 
  * of type `R`.
  */
case class PatFunc2[V1, V2, R](
  v1: Var2_1[V1, V2], 
  v2: Var2_2[V1, V2], 
  body: Pat2[V1, V2, R]
) {
  def graft(arg1: Pat[V1], arg2: Pat[V2]): Pat[R] = 
    body.graft(Graft(v1, arg1, v2, arg2))
}

/** A pattern that represents non-closed
  * expression with holes of two types `V1` and `V2`,
  * which, once some patterns are plugged into the
  * holes, evaluates to a value of type `A`.
  */
sealed trait Pat2[V1, V2, A] {
  def graft(g: Graft2[V1, V2]): Pat[A]
}

case class IntPat2[V1, V2](i: Int) extends Pat2[V1, V2, Int] {
  def graft(g: Graft2[V1, V2]): Pat[Int] = IntPat(i)
}

case class Var2_1[V1, V2](name: String) extends Pat2[V1, V2, V1] {
  def graft(g: Graft2[V1, V2]): Pat[V1] = g(this) // no cast!
}

case class Var2_2[V1, V2](name: String) extends Pat2[V1, V2, V2] {
  def graft(g: Graft2[V1, V2]): Pat[V2] = g(this) // no cast!
}

case class BinopPat2[V1, V2, A, B, C](
  a: Pat2[V1, V2, A], 
  b: Pat2[V1, V2, B], 
  op: (A, B) => C
) extends Pat2[V1, V2, C] {
  def graft(g: Graft2[V1, V2]): Pat[C] = BinopPat(a graft g, b graft g, op)
}

/** Grafting operation that can fill holes of two types
  * `V1` and `V2` in expressions with free variables of
  * those two types.
  */
trait Graft2[V1, V2] {
  def apply(v1: Var2_1[V1, V2]): Pat[V1]
  def apply(v2: Var2_2[V1, V2]): Pat[V2]
}

object Graft {
  /** Helper method to simplify the construction 
    * of a `Graft2` when there are exactly two
    * variables.
    */
  def apply[V1, V2](
    v1: Var2_1[V1, V2], arg1: Pat[V1], 
    v2: Var2_2[V1, V2], arg2: Pat[V2]
  ): Graft2[V1, V2] = new Graft2[V1, V2] {
    def apply(w1: Var2_1[V1, V2]): Pat[V1] = {
      if (v1 == w1) arg1
      else throw new NoSuchElementException("No binding for variable " + w1)
    }
    def apply(w2: Var2_2[V1, V2]): Pat[V2] = {
      if (v2 == w2) arg2
      else throw new NoSuchElementException("No binding for variable " + w2)
    }
  }
}

val test = FoldLeft(
  List(IntPat(1), IntPat(2), IntPat(3)), 
  IntPat(42), 
  {
    val a = Var2_1[Int, Int]("a")
    val b = Var2_2[Int, Int]("b")
    PatFunc2(a, b, BinopPat2(a, b, (_: Int) + (_: Int)))
  }
)

println(test.eval)

这将打印以下符号评估的 AST（我修复了缩进并将丑陋的匿名 lambda 名称 _ + _ 替换为 +Lambda）：

BinopPat(
  BinopPat(
    BinopPat(
      IntPat(42), IntPat(1), +Lambda
    ),
    IntPat(2), +Lambda
  ),
  IntPat(3), +Lambda
)

我希望这大致就是您希望在代码中实现的目标。至少这是我从您的编辑和评论中了解到的。

请注意，我在代码片段中到处都使用了 "graft" 而不是 "substitute"。嫁接是一个更简单的term-rewriting 操作，因为它忽略了变量名捕获的问题。如果您开始在函数内部使用函数，它可能会开始表现得很奇怪，因为变量名称可能会冲突。

此外，如果你采用这种方法，你将需要像 Graft1、Graft2、...、Graft22 这样的东西，因为你实际上是在为 Function1, ..., Function22 在标准库中。但是，请注意，我的 Graft2 实现可以也基于变量名进行调度，因此 2 是 类型的数量 个变量，而不是不同变量的数量（不同变量的数量可以大于 2）。

如果这一切都太尴尬了，您可以改为：将变量名放在一起并使用普通的 Scala 闭包。

与 HKT 的模式匹配 - 避免强制转换 return 类型

Pattern matching with HKT - avoid having to cast return type

scala

pattern-matching

higher-kinded-types