用于检查参数值的 Scala 类型约束

Question

我正在尝试在 Scala 中实现 Conway 的 surreal numbers。超现实数是递归定义的——作为一对超现实数集，称为左和右，使得右集中的任何元素都不小于或等于左集中的任何元素。这里超现实数之间的“小于或等于”关系也是递归定义的：我们说 x ≤ y if

x 的左集合中没有元素 a 使得 y ≤ 一个，和
y的右集合中没有元素b使得b≤ x.

我们从将零定义为一对空集开始，然后用零定义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]

用于检查参数值的 Scala 类型约束

Scala type constraint to check argument values

types

scala

type-level-computation

shapeless

scala-macros