Scala 类型约束来检查参数值

Question

我正在尝试在 Scala 中实现康威的超现实数字。超现实数是递归定义的——作为一对超现实数的集合，称为左和右，这样右集中的任何元素都不小于或等于左集中的任何元素。这里超现实数之间的关系“小于或等于”也是递归定义的：我们说x ? Ÿ如果

• 在x的左集中没有元素a使得y ? 一，和
• 在y的右集中没有元素b使得b ? ×。

我们首先将零定义为一对空集，然后使用零来定义 1 和 -1，依此类推。

我无法弄清楚如何在编译时强制执行超现实数字的定义。这就是我现在所拥有的：

case class SurrealNumber(left: Set[SurrealNumber], right: Set[SurrealNumber]) {
  if ((for { a <- left; b <- right; if b <= a } yield (a, b)).nonEmpty)
    throw new Exception
  def <=(other: SurrealNumber): Boolean =
    !this.left.exists(other <= _) && !other.right.exists(_ <= this)
}

val zero = SurrealNumber(Set.empty, Set.empty)
val one = SurrealNumber(Set(zero), Set.empty)
val minusOne = SurrealNumber(Set.empty, Set(zero))

assert(zero <= zero)
assert((zero <= one) && !(one <= zero))
assert((minusOne <= zero) && !(zero <= minusOne))

当参数无效时，如在 中SurrealNumber(Set(one), Set(zero))，此代码将引发运行时异常。是否可以将有效性检查表示为类型约束，从而SurrealNumber(Set(one), Set(zero))无法编译？

Answer 1

您可以定义一个宏以便在编译时执行计算

case class SurrealNumber private(left: Set[SurrealNumber], right: Set[SurrealNumber]) {
  def <=(other: SurrealNumber): Boolean =
    !this.left.exists(other <= _) && !other.right.exists(_ <= this)
}

object SurrealNumber {
  def unsafeApply(left: Set[SurrealNumber], right: Set[SurrealNumber]): SurrealNumber =
    new SurrealNumber(left, right)

  def apply(left: Set[SurrealNumber], right: Set[SurrealNumber]): SurrealNumber =
    macro applyImpl

  def applyImpl(c: blackbox.Context)(left: c.Tree, right: c.Tree): c.Tree = {
    import c.universe._
    def eval[A](t: Tree): A = c.eval(c.Expr[A](c.untypecheck(t)))
    val l = eval[Set[SurrealNumber]](left)
    val r = eval[Set[SurrealNumber]](right)
    if ((for { a <- l; b <- r; if b <= a } yield (a, b)).nonEmpty)
      c.abort(c.enclosingPosition, "invalid surreal number")
    else q"SurrealNumber.unsafeApply($left, $right)"
  }
}

但问题是，虽然

SurrealNumber(Set.empty, Set.empty)

是的编译时间值zero，但

SurrealNumber(Set(zero), Set.empty)
SurrealNumber(Set.empty, Set(zero))

是 的运行时值one，minusOne编译器无权访问它们。所以

SurrealNumber(Set(SurrealNumber(Set.empty, Set.empty)), Set.empty)
SurrealNumber(Set.empty, Set(SurrealNumber(Set.empty, Set.empty)))

编译但是

SurrealNumber(Set(zero), Set.empty)
SurrealNumber(Set.empty, Set(zero))

别。

因此，您应该重新设计SurrealNumber以提高类型级别。例如

import shapeless.{::, HList, HNil, IsDistinctConstraint, OrElse, Poly1, Poly2, Refute, poly}
import shapeless.ops.hlist.{CollectFirst, LeftReducer}
import shapeless.test.illTyped

class SurrealNumber[L <: HList : IsDistinctConstraint : IsSorted, 
                    R <: HList : IsDistinctConstraint : IsSorted](implicit
  notExist: Refute[CollectFirst[L, CollectPoly[R]]]
)

trait LEq[S, S1]
object LEq {
  implicit def mkLEq[S,  L  <: HList,  R <: HList, 
                     S1, L1 <: HList, R1 <: HList](implicit
    ev:        S  <:< SurrealNumber[L, R],
    ev1:       S1 <:< SurrealNumber[L1, R1],
    notExist:  Refute[CollectFirst[L, FlippedLEqPoly[S1]]],
    notExist1: Refute[CollectFirst[R1, LEqPoly[S]]]
  ): S LEq S1 = null
}

trait CollectPoly[R <: HList] extends Poly1
object CollectPoly {
  implicit def cse[R <: HList, LElem](implicit 
    exist: CollectFirst[R, LEqPoly[LElem]]
  ): poly.Case1.Aux[CollectPoly[R], LElem, Unit] = null
}

trait LEqPoly[FixedElem] extends Poly1
object LEqPoly {
  implicit def cse[FixedElem, Elem](implicit 
    leq: Elem LEq FixedElem
  ): poly.Case1.Aux[LEqPoly[FixedElem], Elem, Unit] = null
}

trait FlippedLEqPoly[FixedElem] extends Poly1
object FlippedLEqPoly {
  implicit def cse[FixedElem, Elem](implicit 
    leq: FixedElem LEq Elem
  ): poly.Case1.Aux[FlippedLEqPoly[FixedElem], Elem, Unit] = null
}

object isSortedPoly extends Poly2 {
  implicit def cse[Elem, Elem1](implicit 
    leq: Elem LEq Elem1
  ): Case.Aux[Elem, Elem1, Elem1] = null
}
type IsSorted[L <: HList] = (L <:< HNil) OrElse LeftReducer[L, isSortedPoly.type]

val zero = new SurrealNumber[HNil, HNil]
val one = new SurrealNumber[zero.type :: HNil, HNil]
val minusOne = new SurrealNumber[HNil, zero.type :: HNil]
illTyped("new SurrealNumber[one.type :: HNil, zero.type :: HNil]")
new SurrealNumber[zero.type :: HNil, one.type :: HNil]