3

我正在尝试在 Scala 中对代数半环进行建模。我遇到了类型转换问题，这使得我无法在 Scala 中做我想做的事情。我希望有人可以指导我了解我误解的 Scala 打字系统方面。

（请耐心等待这个问题的长时间设置。我已经尽可能地减少了它。）

半环是一组项目，在其上定义了二进制加法 (+) 和乘法 (*) 运算符及其标识元素，分别称为零和一。例如，整数半环定义在整数上，其中 + 和 * 是算术的标准运算，零和一个是整数 0 和 1。一个更奇特的例子是布尔半环，它是在值 True 和 False 上定义的，其中+是逻辑或，*是逻辑与，零是假，一是真。

为了对此建模，我定义了一个特征，该特征指定了适当的二元运算符。

trait SemiringElement {
  /**
   * The element type
   */
  type E
  /**
   * The type returned by the the addition and multiplication operators
   */
  type R <: SemiringElement
  val value: E

  def +(that: R): R

  def *(that: R): R

  override def toString = value.toString
}

案例类实例化特定半环的元素。例如，布尔半环看起来像这样。

case class BooleanSemiringElement(init: Boolean) extends SemiringElement {
  type E = Boolean
  type R = BooleanSemiringElement
  val value = init

  def +(that: BooleanSemiringElement#R) = BooleanSemiringElement(value || that.value)

  def *(that: BooleanSemiringElement#R) = BooleanSemiringElement(value && that.value)
}

我还有一个 Semiring 特征，它指定零和一个元素。

trait Semiring {
  type E <: SemiringElement
  /**
   * The addition identity
   */
  val zero: E
  /**
   * The multiplication identity
   */
  val one: E
}

特定的半环对象返回相应类型的零和一元素。

object BooleanSemiring extends Semiring {
  type E = BooleanSemiringElement

  val zero = BooleanSemiringElement(false)
  val one = BooleanSemiringElement(true)
}

Semiring 对象本质上是工厂单例，它们知道如何返回适当类型的标识元素。

我希望能够编写通常与半环元素一起使用的算法。我使用 Semiring 工厂对象是为了能够在运行时而不是编译时指定特定的半环。例如，假设我有一个对象维护字符串和半环元素之间的映射。

class ElementMap(s: Semiring) {
  val m = mutable.Map[String, SemiringElement]()
}

如果我用这样的调用实例化它：

val x = new ElementMap(BooleanSemiring)

我希望 xm 成为 String->BooleanSemiringElement 映射。问题是我实际上是一个 String->SemiringElement 映射。

scala> val x = new ElementMap(BooleanSemiring)
x: ElementMap = ElementMap@46cf97b
scala> x.m
res2: scala.collection.mutable.Map[String,SemiringElement] = Map()
scala> x.m("one") = BooleanSemiring.one
scala> x.m("one") + BooleanSemiring.one
<console>:12: error: type mismatch;
 found   : BooleanSemiring.one.type (with underlying type BooleanSemiring.BooleanSemiringElement)
 required: _1.R where val _1: SemiringElement
              x.m("one") + BooleanSemiring.one
                                       ^

如果我愿意在编译时而不是运行时指定类型，我可以使元素类型成为通用类型，如下所示：

class ElementMap[BooleanSemiring]...

但是我需要一个工厂方法来创建所有不同类型的 ElementMap 对象。将工厂智能放入 Semiring 特质中在架构上更有意义。我想说的是这样的：

class ElementMap(s: Semiring) {
  val m = mutable.Map[String, s.E]()
}

即：创建从字符串到提供给构造函数的 Semiring 对象返回的元素类型 E 的映射。我不知道该怎么做。我尝试了各种语法技巧和隐式转换都无济于事。

有没有办法编写一个在运行时配置有 Semiring 构造函数参数的 ElementMap，还是我采取了错误的方法？我是 Scala 的新手，并试图以 Scala 风格的方式做事。我觉得我在这里把自己画到了一个角落里，但我不确定错误到底在哪里。

4

1 回答 1

0

您是否尝试过将特定类型捕获s为类型参数？

scala> class ElementMap[S <: Semiring](s: S) {
     |   val m = collection.mutable.Map[String, S#E]()
     | }
defined class ElementMap

scala> val x = new ElementMap(BooleanSemiring)
x: ElementMap[BooleanSemiring.type] = ElementMap@6544c984

scala> x.m("one") = BooleanSemiring.one

scala> x.m("one") + BooleanSemiring.one
res0: BooleanSemiringElement = true

您可以对元素类型执行类似的操作：

scala> class ElementMap[SE <: SemiringElement](s: Semiring { type E = SE }) {
     |   val m = collection.mutable.Map[String, SE]()
     | }
defined class ElementMap

scala> val x = new ElementMap(BooleanSemiring)
x: ElementMap[BooleanSemiringElement] = ElementMap@4cf353e5

scala> x.m("one") = BooleanSemiring.one

scala> x.m("one") + BooleanSemiring.one
res1: BooleanSemiringElement = true

您的版本的问题在于您丢弃了所有关于的类型信息s——从 . 的角度来看ElementMap，它只是一个Semiring.

（作为旁注，通过类型类的临时多态性可能是在 Scala 中解决此问题的一种更自然的方法。例如，参见Scalaz 7表示类似代数结构的方式。）

于 2012-10-02T20:46:06.127 回答