seratch's weblog in Japanese

About Scala, Java and Ruby programming in Japaense. If you need English information, go to http://blog.seratch.net/

Scala School意訳(Advanced types)

http://twitter.github.com/scala_school/advanced-types.html

以下は私の方でtypoや表示崩れを直したものです。

https://github.com/seratch/scala_school/blob/master/web/_posts/2011-05-06-lesson.textile

誤訳などありましたら、お手数ですが、ご指摘いただければ幸いです。

事前知識

いきなりScala Schoolの和訳に入る前にまずビュー(view)について少し補足します。

ここでのビュー(view)は、コレクションの遅延評価(SeqView)とは別物です。

scala> (1 to 100).view
res42: java.lang.Object with scala.collection.SeqView[Int,scala.collection.immutable.IndexedSeq[Int]] = SeqView(...)

scala> (1 to 100).view filter ( _ % 17 == 0 ) force
res43: scala.collection.immutable.IndexedSeq[Int] = Vector(17, 34, 51, 68, 85)

http://www.scala-lang.org/api/current/scala/collection/SeqView.html

ここでいうビューとは、端的には暗黙の型変換(implicit conversions)のことを指します。

オライリー本によると「ビューは、型Aを型Bに変換する暗黙の関数値」とあります。
具体的には「A => B」「(=> A) => B」という型になります(「=> A」は名前渡しです)。

ビューが適用される条件は以下の二つです。

  1. 型Bが期待されるコンテキストで型Aが使われ、スコープ内にAをBに変換するビューが存在する
  2. 型Aに存在しないメンバーmが参照され、スコープ内にAを(メンバーmを持つ)Bに変換するビューが存在する

では、ビューといえる関数は、具体的にどういうものかというと、例えばscala.Predefに「implicit def 〜」でたくさん定義されています。

https://github.com/scala/scala/blob/master/src/library/scala/Predef.scala

たとえば、Predef.scalaにある以下のimplicit宣言は1.のパターンで

implicit def double2Double(x: Double) = java.lang.Double.valueOf(x)

型推論scala.Doubleな値にjava.lang.Doubleが要求された場合に適用されることになります。

scala> val d: Double = 1.0d
d: Double = 1.0

scala> val jd: java.lang.Double = d
jd: java.lang.Double = 1.0

2.のパターンの例は、「Map("foo" -> 123)」のようなMapの初期化構文です(オライリー本 7.1)。「->」呼び出しをタプルに変換するビューがPredefに定義されているので

class ArrowAssoc[A](leftOfArrow: A) { 
  def -> [B](y: B): Tuple2[A, B] = Tuple2(leftOfArrow, y)
}
implicit def any2ArrowAssoc[A](x: A): ArrowAssoc[A] = new ArrowAssoc(x)

「x.->(y)」という構文が(x, y)のタプルに変換されることになります。

以上を踏まえた上で、Scala Schoolに戻ります。

View bounds (“type classes”)

Scalaでのimplicit宣言された関数は、型推論を満たす場合にオンデマンドに関数を適用することを可能にします。例としては以下の通りです。

scala> implicit def strToInt(x: String) = x.toInt
strToInt: (x: String)Int

scala> "123"
res0: java.lang.String = 123

scala> val y: Int = "123"
y: Int = 123

scala> math.max("123", 111)
res1: Int = 123

ビュー(可視)境界は与えられた型についてこのような関数(implicitな関数)が存在するかどうか求めます。

scala> class Container[A <% Int] { def addIt(x: A) = 123 + x }
defined class Container

「[A <% Int]」はA型がInt型として見る(view)ことができる必要があることを示します。それでは試してみましょう。

scala> (new Container[String]).addIt("123")
res11: Int = 246

scala> (new Container[Int]).addIt(123) 
res12: Int = 246

scala> (new Container[Float]).addIt(123.2F)
<console>:8: error: could not find implicit value for evidence parameter of type (Float) => Int
       (new Container[Float]).addIt(123.2)
        ^

Other type bounds

メソッドは型にある特定の証拠を求める場合があります(証拠パラメータ)。

A =:= B:AはBと等しくなくてはならない
A <:< B:AはBのサブ型ではなくてはならない
// A <%< B:AはBとして見る(view)ことができなければならない ※2.9.1時点で非推奨
A => B:AはBとしてとして見る(view)ことができなければならない

scala> class Container[A](value: A) { def addIt(implicit evidence: A =:= Int) = 123 + value }
defined class Container

scala> (new Container(123)).addIt
res11: Int = 246

(訳者追記)AがString型になった時点では問題ありませんが

scala>  (new Container("123"))
res12: Container[java.lang.String] = Container@6a92e96c

(訳者追記)Container#addItを呼び出しがある場合はコンパイル時に「A =:= Int」が検証されてコンパイルエラーになります。

scala> (new Container("123")).addIt
//<console>:10: error: could not find implicit value for parameter evidence: =:=[java.lang.String,Int]
<console>:10: error: Cannot prove that java.lang.String =:= Int.
       (new Container("123")).addIt
                              ^

前に定義したimplicit宣言によって可視の制約を緩めることができます。

// scala> class Container[A](value: A) { def addIt(implicit evidence: A <%< Int) = 123 + value }
// defined class Container
// --- in Scala 2.9.1 ---
// <console>:8: warning: class <%< in object Predef is deprecated: Use From => To instead
//       class Container[A](value: A) { def addIt(implicit evidence: A <%< Int) = 123 + value }
//                                                                     ^
scala> class Container[A](value: A) { def addIt(implicit evidence: A => Int) = 123 + value }
defined class Container

scala> (new Container("123")).addIt
res15: Int = 246

(訳者追記)

証拠パラメータ(evidence parameter)は「Generalized Type Constraints」とも呼ばれます。また、上記にも反映してありますが「<%<」はScala 2.9.1時点でdeprecatedになっているので代わりに「=>」を使います。

ビュー(可視)境界(view bounds)と証拠パラメータ(evidence parameter)についてのコップ本での例をもとに補足します。

def maxList[T](elements: List[T])(implicit orderer: T => Ordered[T]): T = {
  elements match {
    case List() => throw new IllegalArgumentException("empty list!")
    case List(x) => x
    case x :: rest => {
      val maxRest: T = maxList(rest) // maxList(rest)(orderer)
      if (x > maxRest) x // orderer(x)
      else maxRest
    }
  }
}

scala> maxList(List(1,3,2))
res0: Int = 3

scala> maxList(List("1","3","2"))
res1: java.lang.String = 3

一見、implicitなパラメータは不要にみえるかもしれませんが、実際にやってみると以下のようにコンパイルエラーになります。

scala> def maxList[T](elements: List[T]): T = {
     |   elements match {
     |     case List() => throw new IllegalArgumentException("empty list!")
     |     case List(x) => x
     |     case x :: rest => {
     |       val maxRest: T = maxList(rest) // maxList(rest)(orderer)
     |       if (x > maxRest) x // orderer(x)
     |       else maxRest
     |     }
     |   }
     | }
<console>:14: error: value > is not a member of type parameter T
             if (x > maxRest) x // orderer(x)

IntやStringなどの型であれば、Orderedへの変換はあらかじめビュー(implicit関数)が存在しているので「x > maxRest」を実行することができます。

これはT型を暗黙にOrdered[T]型に変換してくれるビューが前提条件になります。先ほどのimplicitパラメータはこのことを定義しているということになります。これが証拠パラメータ(evidence parameter)です。

val i: Ordered[Int] = 12345
val str: Ordered[String] = "foo"
val c: Ordered[Char] = 'a'

一方、ビューが存在しない型の場合、以下のようにコンパイルエラーになります。

case class NotOrderable(value: Int)
maxList(List(NotOrderable(2),NotOrderable(3),NotOrderable(1)))

scala> maxList(List(NotOrderable(2),NotOrderable(3),NotOrderable(1)))
<console>:11: error: No implicit view available from NotOrderable => Ordered[NotOrderable].
              maxList(List(NotOrderable(2),NotOrderable(3),NotOrderable(1)))
                     ^

このような「Ordered[T]として扱える任意のTを扱う」という例は非常に良くあるパターンなので、下のように書けるようにしたのがビュー(可視)境界です。内容は同じで、記述の仕方が違うだけです。

def maxList[T <% Ordered[T]](elements: List[T]): T = // ...

以下は、Scala 2.8 言語仕様の和訳です。「7.4 コンテキスト境界と可視境界(ビュー境界)」に説明があります。
http://www.scala-lang.org/docu/files/LangSpec2.8-ja_JP.pdf

Generic programming with views
ビューは、Scalaの標準ライブラリでは主にコレクションについての汎用な関数の実装に使われています。

例えばmin関数ではこのようなテクニックを使っています。

def min[B >: A](implicit cmp: Ordering[B]): A = {
  if (isEmpty)
    throw new UnsupportedOperationException("empty.min")

  reduceLeft((x, y) => if (cmp.lteq(x, y)) x else y)
}

この実装における主な利点は以下の二点です。

1. 各要素はOrderedを実装していなくてよいが、Orderedが使われることは静的に型チェックがされる
2. ライブラリによる追加のサポートなしで自前のOrderingを定義することができる

scala> List(1,2,3,4).min
res0: Int = 1

scala> List(1,2,3,4).min(new Ordering[Int] { def compare(a: Int, b: Int) = b compare a })
res3: Int = 4

注釈にあるように標準ライブラリにはOrderedをOrderingに転換するビューがあります(逆もまた然りです)。

trait LowPriorityOrderingImplicits {
  implicit def ordered[A <: Ordered[A]]: Ordering[A] = new Ordering[A] {
    def compare(x: A, y: A) = x.compare(y)
  }
}
Context bounds & implicitly[]
Scala 2.8 は暗黙のパラメータを行き渡らせたり、アクセスしたりするための略記法を導入しました。

scala> def foo[A](implicit x: Ordered[A]) {}
foo: [A](implicit x: Ordered[A])Unit

scala> def foo[A : Ordered] {}                        
foo: [A](implicit evidence$1: Ordered[A])Unit

「implicitly」というキーワードを使ってアクセスされる場合もあります。

scala> implicitly[Ordering[Int]]
res37: Ordering[Int] = scala.math.Ordering$Int$@3a9291cf

これらを組み合わせることで、特にビューが行き渡っているときにより少ないコードで実装することができます。

(訳者追記)

val ordering = implicitly[Ordering[Int]]
ordering.compare(4,2) // 1
ordering.compare(5,5) // 0
ordering.compare(3,6) // -1

Higher-kinded types & ad-hoc polymorphism

Scalaは高階な型(higher kinded type)を抽象化します。これはに関数のカリー化に似たものです。

例として、まず以下のような単一な型パラメータを持っているものについてですが

List[A]

この例では、具体的な型を生み出すためには一階層の型変数を指定しなければなりません(まるでカリー化されていない関数が一つの引数リストによって起動される必要があるのと同じです)。

高階型ではもっと多くの型を指定する必要があります。

scala> trait Container[M[_]] { def put[A](x: A): M[A]; def get[A](m: M[A]): A }

scala> new Container[List] { def put[A](x: A) = List(x); def get[A](m: List[A]) = m.head }
res23: java.lang.Object with Container[List] = $anon$1@7c8e3f75

scala> res23.put("hey")
res24: List[java.lang.String] = List(hey)

scala> res23.put(123)  
res25: List[Int] = List(123)

Container型がパラメータ化された型においてポリモーフィックであることに注意してください。

implicitを使うコンビネータ(抽出子)を結合すれば、アドホックなポリモーフィズム(=コンテナをまたがって汎用な関数を書ける能力といえます)を手に入れることができます。

scala> trait Container[M[_]] { def put[A](x: A): M[A]; def get[A](m: M[A]): A }

scala> implicit val listContainer = new Container[List] { def put[A](x: A) = List(x); def get[A](m: List[A]) = m.head }

scala> implicit val optionContainer = new Container[Some] { def put[A](x: A) = Some(x); def get[A](m: Some[A]) = m.get }

scala> def tupleize[M[_]: Container, A, B](fst: M[A], snd: M[B]) = {
     | val c = implicitly[Container[M]]                             
     | c.put(c.get(fst), c.get(snd))
     | }
tupleize: [M[_],A,B](fst: M[A],snd: M[B])(implicit evidence$1: Container[M])M[(A, B)]

scala> tupleize(Some(1), Some(2))
res33: Some[(Int, Int)] = Some((1,2))

scala> tupleize(List(1), List(2))
res34: List[(Int, Int)] = List((1,2))

F-bounded polymorphism

(汎用な)トレイトで具象となるサブクラスへのアクセスがよく必要となります。

例えば、ある汎用なトレイトがあって、しかし、それがそのトレイトの特定のサブクラスと比較できるというケースを考えてみましょう。

trait Container extends Ordered[Container]

Containerはcompareメソッドを必要とします。

def compare(that: Container): Int

そして、具象クラスとなるサブ型にはアクセスできません。このように

class MyContainer extends Container {
  def compare(that: MyContainer): Int = 0
}

Orderedの型パラメータにサブ型(MyContainer)ではなくContainerを指定しているので、これはコンパイルに失敗します。

// 訳者追記:ContainerはOrdered[Container]のサブ型なので
// そのサブ型であるMyContainerもOrdered[MyContainer]ではなく、Ordered[Container]になっています

scala> class MyContainer extends Container {
     |   def compare(that: MyContainer): Int = 0
     | }
<console>:14: error: class MyContainer needs to be abstract, since method compare in trait Ordered of type (that: Container)Int is not defined
(Note that A does not match MyContainer)
       class MyContainer extends Container {
             ^

これを調整するために、F-有界なポリモーフィズムを使います。

trait Container[A <: Container[A]] extends Ordered[A]

奇妙な型ですね!しかし、Orderedがそれ自身がContainer[A]であるAをどのようにパラメータ化しているかに注目してみてください。

これによって

class MyContainer extends Container[MyContainer] { 
  def compare(that: MyContainer) = 0 
}

並び替えが可能になりました。

scala> List(new MyContainer, new MyContainer, new MyContainer)
res3: List[MyContainer] = List(MyContainer@30f02a6d, MyContainer@67717334, MyContainer@49428ffa)

scala> List(new MyContainer, new MyContainer, new MyContainer).min
res4: MyContainer = MyContainer@33dfeb30

もしそれが全てContainer[_]のサブ型であれば、他のサブクラスを定義したり、ミックスしたContainer[_]のリストをつくることができます。

scala> class YourContainer extends Container[YourContainer] { def compare(that: YourContainer) = 0 }
defined class YourContainer

scala> List(new MyContainer, new MyContainer, new MyContainer, new YourContainer)
res2: List[Container[_ >: YourContainer with MyContainer <: Container[_ >: YourContainer with MyContainer <: ScalaObject]]] 
  = List(MyContainer@3be5d207, MyContainer@6d3fe849, MyContainer@7eab48a7, YourContainer@1f2f0ce9)

結果の型が「YourContainer with MyContainer」によって下限境界が指定されていることに注目してください。
これは型推論による仕業です。興味深いことにこの型は筋が通っている必要さえありません。
単にリストの統合された型について論理的に最大の下限境界を提供しているだけです。
それではこの状態でOrderedを使おうとすると何が起きるのでしょうか?

// (new MyContainer, new MyContainer, new MyContainer, new YourContainer).min
// <console>:9: error: could not find implicit value for parameter cmp:
//   Ordering[Container[_ >: YourContainer with MyContainer <: Container[_ >: YourContainer with MyContainer <: ScalaObject]]]
scala> List(new MyContainer, new MyContainer, new MyContainer, new YourContainer).min
<console>:11: error: diverging implicit expansion for type Ordering[Container[_ >: YourContainer with MyContainer <: Container[_ >: YourContainer with MyContainer <: ScalaObject]]]
starting with method ordered in trait LowPriorityOrderingImplicits
       List(new MyContainer, new MyContainer, new MyContainer, new YourContainer).min
                                                                                  ^

統合された型にはOrdered[]が存在しないようです。残念。

Structural types

Scalaは構造的型(型の条件は具象の型ではなくインタフェース構造で示されます)をサポートしています。

scala> def foo(x: { def get: Int }) = 123 + x.get
foo: (x: AnyRef{def get: Int})Int

scala> foo(new { def get = 10 })                 
res0: Int = 133

これは多くの場面において非常に素晴らしい機能なのですが、その実装はリフレクションを使っています。
使う場合はパフォーマンスに注意しましょう!

(訳者追記)

Scalaでいわゆるダックタイピングをするための機能です。

Abstract type members

トレイトではtype変数を抽象のままにしておくことができます。

scala> trait Foo { type A; val x: A; def getX: A = x }
defined trait Foo

scala> (new Foo { type A = Int; val x = 123 }).getX   
res3: Int = 123

scala> (new Foo { type A = String; val x = "hey" }).getX
res4: java.lang.String = hey

これはDI(依存性注入)などに便利なトリックです。
抽象なtype変数をハッシュ・オペレータを使って参照することができます。

scala> trait Foo[M[_]] { type t[A] = M[A] }
defined trait Foo

scala> val x: Foo[List]#t[Int] = List(1)
x: List[Int] = List(1)

Type erasures & manifests

ご存知の通り、型情報はコンパイル時に消去されるので失われます。
Scalaは型情報を選択的に復元できるManifestを用意しています。
Manifestは必要に応じてコンパイラによって生成され、implicitな値として提供されます。

scala> class MakeFoo[A](implicit manifest: Manifest[A]) { def make: A = manifest.erasure.newInstance.asInstanceOf[A] }

scala> (new MakeFoo[String]).make 
res10: String = ""

Case study: Finagle

https://github.com/twitter/finagle

trait Service[-Req, +Rep] extends (Req => Future[Rep])

trait Filter[-ReqIn, +RepOut, +ReqOut, -RepIn]
  extends ((ReqIn, Service[ReqOut, RepIn]) => Future[RepOut])
{
  def andThen[Req2, Rep2](next: Filter[ReqOut, RepIn, Req2, Rep2]) =
    new Filter[ReqIn, RepOut, Req2, Rep2] {
      def apply(request: ReqIn, service: Service[Req2, Rep2]) = {
        Filter.this.apply(request, new Service[ReqOut, RepIn] {
          def apply(request: ReqOut): Future[RepIn] = next(request, service)
          override def release() = service.release()
          override def isAvailable = service.isAvailable
        })
      }
    }
    
  def andThen(service: Service[ReqOut, RepIn]) = new Service[ReqIn, RepOut] {
    private[this] val refcounted = new RefcountedService(service)

    def apply(request: ReqIn) = Filter.this.apply(request, refcounted)
    override def release() = refcounted.release()
    override def isAvailable = refcounted.isAvailable
  }    
}

認証が必要なリクエストをフィルターで処理します。

trait RequestWithCredentials extends Request {
  def credentials: Credentials
}

class CredentialsFilter(credentialsParser: CredentialsParser)
  extends Filter[Request, Response, RequestWithCredentials, Response]
{
  def apply(request: Request, service: Service[RequestWithCredentials, Response]): Future[Response] = {
    val requestWithCredentials = new RequestWrapper with RequestWithCredentials {
      val underlying = request
      val credentials = credentialsParser(request) getOrElse NullCredentials
    }
    service(requestWithCredentials)
  }
}

下層サービスは認証処理済のリクエストを要求し、しかも、それは静的に検証されるのです。
フィルターはサービスの変換器のように捉えることができます。

たくさんのフィルターをcomposeすることができます。

val upFilter =
  logTransaction     andThen
  handleExceptions   andThen
  extractCredentials andThen
  homeUser           andThen
  authenticate       andThen
  route

Type safely!