(皿うどん)Structural Subtyping(構造的部分型)アレコレ

このまえ、夢の中でね、あるコレクションの中から特定のシグニチャを持つオブジェクトをより分けるようなコード書いてる夢見たんですよ。ええ、見たんです夢で。

で、ふと目が覚めて(深夜3時半)おもむろにREPLでいろいろやってみた結果を書こうと思います。ええ、書いてみます。

Structural Subtyping(構造的部分型)って何ぞ?

例から入ります。あるメソッドのシグニチャ(名前、引数の例えば{def mkString (start:String, sep:String, end:String):String}というシグニチャを持つ型Aを定義すると、上記のシグニチャを持つ型Bや型CはAの派生型と見なされるわけです。

このように、2つの型がもつメソッドなどの構造によって派生関係が決まるのがStructural Subtyping(構造的部分型)というものです。対して、通常のextendsなどの宣言によって派生関係を決定するのはNominal Subtyping(公称型)といいます。OCamlをご存じの方にはおなじみだと思います。

さて、このStructural Subtypingを用いることで静的なduck typingが可能になります。特定のシグニチャを持つオブジェクトのみを引数として受け入れるメソッドとかが定義できちゃって、コンパイル時に型チェックしてくれるわけですね。

さっきの例で、mkStringというString3つを引数に取ってStringを返すメソッドを持つ型として、Stringify型を定義します。ちなみに、指定できるメソッドは複数でも構いません(ついでにtoStringも追加してみました意味ないけど)。複数指定した場合は全てのシグニチャを満たさないと派生型と見なされませんので。

scala> type Stringify = {
     |   def mkString (start:String, sep:String, end:String):String  
     |   def toString:String
     | }
defined type alias Stringify

では、このStringify型を利用して、def mkString (start:String, sep:String, end:String):Stringを持つオブジェクトを引数に取るメソッドmkStringWithParenthesesを定義します。

scala> def mkStringWithParentheses(target:Stringify):String = 
     |   target.mkString("(",", ",")")
mkStringWithParentheses: (target: Stringify)String

Stringify型のシグニチャを満たす型として、例えばList[Int]などが考えられます。mkStringWithParenthesesに渡してみましょう。

scala> mkStringWithParentheses( List(1,2,3,4,5) )
res4: String = (1, 2, 3, 4, 5)

問題ないですね。では、Stringify型のシグニチャを満たさない型を与えてみましょう。例えばjava.util.Dateなどです。

scala> mkStringWithParentheses( new java.util.Date )
<console>:8: error: type mismatch;
 found   : java.util.Date
 required: Stringify
       mkStringWithParentheses( new java.util.Date )

mkStringを持っていないのでコンパイルエラーです。やったー！！

ところで、type aliasとして事前にStringify型を定義しましたが、いきなりメソッドの引数の型に書いてしまうこともできます。

scala> def mkStringWithParentheses(target:{def mkString (start:String, sep:String, end:String):String}):String = target.mkString("(",", ",")")
mkStringWithParentheses: (target: AnyRef{def mkString(start: String,sep: String,end: String): String})String

応用編その1 パラメータ化されたStructural Subtyping

Structural Subtypingとして定義しようとしているメソッドが型パラメータを取るように定義されている場合はどうでしょうか? 要素へのランダムアクセスを行えるindexOfを持つ型としてRandomAccessable[A]を定義します。

scala> type RandomAccessable[A] = {
     |   def indexOf[B >: A](elem:B):Int
     | }
defined type alias RandomAccessable

注意点として、Structural Subtypingで定義する型のメソッドないで、その型に渡された型パラメータをメソッド引数に直接利用することはできません。以下のような定義はエラーになります。

scala> type RandomAccessable[A] = {
     |   def indexOf(elem:A):Int
     | }
<console>:6: error: Parameter type in structural refinement may not refer to an abstract type defined outside that refinement
         def indexOf(elem:A):Int

これは型パラメータの共変/反変と同じ考え方で、Aより大きい型パラメータBを導入することで解決できます。

次は、もう少し複雑で、foldLeftとheadを持つ例です。

scala> type FoldLeftfy[A] = {
     |   def foldLeft[B](z: B)(op: (B,A) => B) : B
     |   def head:A
     | }
defined type alias FoldLeftfy

scala> val list:FoldLeftfy[Int] = List(1,2,3)
list: FoldLeftfy[Int] = List(1, 2, 3)

scala> list.foldLeft(0){ _ + _ }
res4: Int = 6

scala> list.reverse
<console>:8: error: value reverse is not a member of FoldLeftfy[Int]
       list.reverse

これは問題なく定義できますし、FoldLeftfy[Int]型のlistに対してfoldLeftを呼び出せます。逆に、reverseなど通常のList型で定義されているメソッドは利用できません。

もちろん、FoldLeftfy型を引数に取る関数も定義できます。以下は、sumおよびmaxを行う関数です。

// implicit parameterでNumericへのimplicit conversionを行う関数numをもらう
def sum[B](xs:FoldLeftfy[B])(implicit num: Numeric[B]) = xs.foldLeft(xs.head){(b,a) => num.plus(b,a) }

// context boundを利用してnumをimplicitlyで取得
def sum[B:Numeric](xs:FoldLeftfy[B]) = xs.foldLeft(xs.head){(b,a) => implicitly[Numeric[B]].plus(a,b) }

// implicit parameterでOrderingへのimplicit conversionを行う関数cmpをもらう
def max[B](xs:FoldLeftfy[B])(implicit cmp: Ordering[B]) = xs.foldLeft(xs.head){(b,a) => if(cmp.gt(b,a)) b else a }

// context boundを利用してcmpをimplicitlyで取得
def max[B:Ordering](xs:FoldLeftfy[B]) = xs.foldLeft(xs.head){(b,a) => if(implicitly[Ordering[B]].gt(b,a)) b else a }

// view boundを利用して、BはOrderedに変換された状態で扱える
def max[B <% Ordered[B]](xs:FoldLeftfy[B]) = xs.foldLeft(xs.head){(b,a) => if( b > a ) b else a } 

応用編その2 型の合成

応用編その1で、RandomAccessableとFoldLeftfyのふたつの型を定義しました。

type FoldLeftfy[A] = {
  def foldLeft[B](z: B)(op: (B,A) => B) : B
  def head:A
}

type RandomAccessable[A] = {
  def indexOf[B >: A](elem:B):Int
}

このふたつの型を同時に満たす型は定義できるのでしょうか?結論から言うと可能です。
以下のようにすればよいのです。

type RandomAccessableFoldLeftfy[A] = RandomAccessable[A] with FoldLeftfy[A]

このRandomAccessableFoldLeftfy[A]は、indexOfとheadとfoldLeftを持っている型になります。以下のように、全てを持っているList[Int]型はRandomAccessableFoldLeftfy[Int]型の変数に代入できますが、indexOfを持たないIterable[Int]型は代入できません。

scala> val list:RandomAccessableFoldLeftfy[Int] = List(1,2,3)                     
list: RandomAccessableFoldLeftfy[Int] = List(1, 2, 3)

scala> val iter:RandomAccessableFoldLeftfy[Int] = List(1,2,3).toIterable     
<console>:8: error: type mismatch;
 found   : Iterable[Int]
 required: RandomAccessableFoldLeftfy[Int]
       val iter:RandomAccessableFoldLeftfy[Int] = List(1,2,3).toIterable

また、通常のtraitとも合成することができます。

scala> type FoldLeftfySet[A] = Set[A] with FoldLeftfy[A]
defined type alias FoldLeftfySet

scala> val set:FoldLeftfySet[String] = Set("foo","bar")
set: FoldLeftfySet[String] = Set(foo, bar)

応用編その3 implicit conversionとの組み合わせ

これはimplicit conversionを利用するのでリスキーですが、implicit conversionの変換元の型としてStructural Subtypingを指定できます。以下のような、FoldLeftfyをwrapするクラスFoldLeftfyProxyを用意し、FoldLeftfy[A]からFoldLeftfyProxy[A]への変換関数を用意します。

scala> class FoldLeftfyProxy[A:Numeric](xs:FoldLeftfy[A]){
     | 
     |   def productAll:A = xs.foldLeft(xs.head){(b,a) => implicitly[Numeric[A]].mkNumericOps(b) * a }
     | }
defined class FoldLeftfyProxy

scala> 

scala> implicit def foldLeftfy2Proxy[A:Numeric](xs:FoldLeftfy[A]) = new FoldLeftfyProxy(xs)
foldLeftfy2Proxy: [A](xs: FoldLeftfy[A])(implicit evidence$1: Numeric[A])FoldLeftfyProxy[A]

FoldLeftfyProxyには、通常のSeqトレイトなどにはないproductAllというメソッドが定義されています。'pimp my libraly'パターンで、List(1,2,3).productAllと呼び出すと、FoldLeftfyProxy[Int]にimplicit conversionで変換されてproductAllが呼び出されるはずです。

scala> List(1,2,3).productAll
res11: Int = 6

ちゃんと動いてますね。ただ、むやみにimplicit conversionで変換しちゃうのは危険なので使いどころ注意ですよ。

注意点 パターンマッチとStructural Subtyping

パターンマッチでStructural Subtpingを指定してもマッチしません。このようなメソッドを用意してコンパイルすると、

  def match_?[A](xs:Traversable[A]) = xs match {
    case xs:FoldLeftfy[A] => true
    case _ => false
  }

こんな警告でます。型情報がイレイジャにより消されるから、パターンマッチしないってわけです。

StructuralSubtyping.scala:36: warning: refinement AnyRef{def foldLeft[B](z: B)(op: (B, A) => B): B; def head: A} in type pattern Main.FoldLeftfy[A] is unchecked since it is eliminated by erasure
    case xs:FoldLeftfy[A] => true
            ^
one warning found

jadってみるとわかりますが、ふつーに消えてます

    public boolean match_$qmark(Traversable xs)
    {
        Traversable traversable = xs;
        return traversable != null;
    }