我正在尝试实现 Conway 的 surreal numbers在斯卡拉。超现实数是递归定义的——作为一对超现实数的集合,称为左和右,这样右集中的任何元素都不小于或等于左集中的任何元素。这里超现实数之间的关系“小于或等于”也是递归定义的:我们说 x ≤ y 如果
我们首先将零定义为一对空集,然后使用零来定义 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))
不会编译?
最佳答案
您可以定义一个宏以便在编译时执行计算
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 类型约束来检查参数值,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/62590645/