scala - 如何在 Scala 中将运行时工厂对象用于半环实现？

Question

我正尝试在 Scala 中模拟代数半环。我遇到了类型转换问题，这些问题使我无法在 Scala 中执行我想执行的操作。我希望有人能指导我了解我误解的 Scala 类型系统方面。

(请耐心等待这个问题的冗长设置。我已经尽可能地减少了它。)

半环是一组项，在这些项上定义了二进制加法 (+) 和乘法 (*) 运算符及其标识元素，分别称为零和一。例如，整数半环是在整数上定义的，其中 + 和 * 是算术和零的标准运算，而一是整数 0 和 1。一个更奇特的例子是 bool 半环，它是在值 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
}

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

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)

我希望 x.m 是一个 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]()
}

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

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

Answer 1

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

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 表示相似代数结构的方式。)