3

Scalaで代数的半環をモデル化しようとしています。型変換の問題が発生しているため、Scalaでやりたいことができないように見えます。私が誤解しているScalaのタイピングシステムの側面を誰かが教えてくれることを願っています。

（この質問の長い設定に耐えてください。私はできる限りそれを減らしました。）

半環は、2進加算（+）および乗算（*）演算子と、それぞれ0および1と呼ばれるそれらの単位元が定義されている項目のセットです。たとえば、整数半環は整数に対して定義されます。ここで、+と*は算術演算の標準演算であり、0と1は整数0と1です。よりエキゾチックな例は、TrueとFalseの値に対して定義されるブール半環です。ここで、+は論理OR、*は論理AND、0はFalse、1はTrueです。

これをモデル化するために、適切な二項演算子を指定する特性を定義します。

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)
}

さらに、0個と1個の要素を指定するSemiring特性があります。

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

特定の半環オブジェクトは、適切なタイプの0個と1個の要素を返します。

object BooleanSemiring extends Semiring {
  type E = BooleanSemiringElement

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

Semiringオブジェクトは、基本的に、適切なタイプのID要素を返す方法を知っているファクトリシングルトンです。

一般的に半環要素で動作するアルゴリズムを記述できるようにしたいと思います。コンパイル時ではなく実行時に特定のセミリングを指定できるようにするために、セミリングファクトリオブジェクトを使用します。たとえば、文字列と半環要素の間のマップを維持するオブジェクトがあるとします。

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 に答える