資料: http://www.scala-lang.org/docu/files/ScalaByExample.pdf
9. Lists
リストの作り方。
val fruit = List("apples", "oranges", "pears") val nums = List(1, 2, 3, 4) val diag3 = List(List(1, 0, 0), List(0, 1, 0), List(0, 0, 1)) val empty = List()
9.1. Using List
この辺はさくさくと。
型は List[T] 。List[String] とか List[Int] とか List[List[Int] ] とか。コンストラクタは Nil と :: 。head 、tail 、isEmpty は普通に使える。
empty.isEmpty = true fruit.isEmpty = false fruit.head = "apples" fruit.tail.head = "oranges" diag3.head = List(1, 0, 0) Nil.head // java.util.NoSuchElementException: head of empty list
パターンマッチも。
{ case Nil => println("nil"), case x::xs => println("cons") }
9.2. Definition of class List I: First Order Methods
abstract class List[+A] 。つまり co-variant 。
主なメソッドの定義の紹介。imEmpty 、head 、tail 、length 、last 、init 、take 、drop 、split 。n 番目を返すメソッドは apply 。apply の syntax sugar によって、xs(0) とか書ける。かっこいい。
zip 。普通。
- もただの識別子。ただし、: で終わる識別子を中置で使った場合は、右のオペランドをレシーバとする呼び出しになる、という特別扱いがある。
x :: y // y.::(x) x + y // x.+(y)
ただし、評価順序はどちらも x 、y の順。あと、: で終わる演算子は結合の優先順位も変わる。
x :: y :: z // x :: (y :: z) x + y + z // (x + y) + z
DSL 野郎は覚えとけ。
- メソッドの定義はこう。
def ::[B >: A](x: B): List[B] = new scala.::(x, this)
ふんふん。クラス名も :: なところが熱いですね。
リストの連結は ::: 。Haskell でいうと ++ のやつ。ただし結合の優先順位は違う。あ、でも Scala の結合順位の方が効率がいいかも？ A ::: B ::: C なら O(A の長さ + B の長さ) だけど、A ++ B ++ C だと O(A の長さ * 2 + B の長さ) になっちゃいそう。
あとは反転。
9.3. Example: Merge sort
スルー
9.4. Definition of class List II: Higher-Order Methods
map の話。
xs map (x => x * factor)
Ruby の each に相当する (値を返さない) のは foreach 。
List(1, 2, 3) foreach println
filter 。
List(1, 2, 3, 4, 5) filter (x => x % 2 == 1) // List(1, 3, 5)
forall と exists 。
List(1, 2, 3, 4, 5) forall (3 ==) // false List(1, 2, 3, 4, 5) exists (3 ==) // true
List.range(n, m) は n から m-1 までのリストを作る。(n...m) みたいな。
List.range(2, 5) // List(2, 3, 4)
reduceLeft と foldLeft 。
List.range(1, 11) reduceLeft { (x, y) => x + y } // 55 (List.range(1, 11) foldLeft 0){ (x, y) => x + y } // 55
reduceRight と foldRight も。
List.range(1, 11) reduceRight { (x, y) => x + y } // 55 (List.range(1, 11) foldRight 0){ (x, y) => x + y } // 55
うーん、{ (x, y) => x + y } が冗長な感じ。
で、ここが熱い。foldLeft と foldRight には /: と :\ という alias がある。
(0 /: List.range(1, 11)) { (x, y) => x + y } // 55 (List.range(1, 11) :\ 0) { (x, y) => x + y } // 55
: がリストをあらわして、スラッシュが下向きの矢印をあらわす AA みたいなイメージで。
あと flatMap 。Haskell の concatMap 。Ruby でも欲しいんだよなこれ。
List(0, 1, 2).flatMap (x => List(x, 42)) // List(0, 42, 1, 42, 2, 42)
10. For-Comprehensions
for 内包表記。集合の内包表記と for ループをつなぐ記法？の話。
name と age のフィールドを持つオブジェクトのリスト persons に対して、以下は同値。
for (p <- persons if p.age > 20) yield p.name person filter (p => p.age > 20) map (p => p.name)
20 歳より年寄りの名前のリストを作る。Python 流の記法かなんかですか？んー、内包表記は Haskell 流のがいいなあ。
for (s) yield e の s には generator と definition と filter が任意個書ける (ただし最初は必ず generator) 。
- generator: val x <- e みたいなもの。ただし e はリスト。
- definition: val x = e みたいなもの。普通の定義と何か違うかは不明。
- filter: Boolean 型の式。これが true のときだけ yield する。
for (x <- List.range(1, 30) if x % 3 != 0 && x % 5 != 0) yield println(x)
んー。
for (s) じゃなくて for {s} でもいいよ。その場合はセミコロンで区切らなくていいよ。
for { i <- List.range(1, 10) j <- List.range(1, i) if isPrime(i+j) } yield (i, j)
といっても for (s) の方でも if p.age > 20 をセミコロンで区切ってないんだけどな。文法がよくわからない。
こういうことも書けるらしい。
for ((x, y) <- xs zip ys) yield x * y
つまり <- の左には任意のパターンが持ってこれるみたい。ということは。
val (x, y) = (1, 2) // 動く val 0 = 0 // 動く val 0 = 1 // scala.MatchError: 1
おお。かなり let と同じなんですね。
10.1. The N-Queens Problem
for 内包表記の使用例 1 。
10.2. Querying with For-Comprehensions
for 内包表記の使用例 2 。
10.3. Translation of For-Comprehensions
for 内包表記がどう実装されているか。以下の 3 つの変換規則で map と flatMap と filter を使う式に変換されるらしい。
for (x <- e) yield e' //==> e.map(x => e') for (x <- e if f; s) yield e' //==> for (x <- e.filter(x => f); s) yield e' for (x <- e; y <- e'; s) yield e'' //==> e.flatMap(x => for (y <- e'; s) yield e'')
なるほど、x <- e if f というのがひとかたまりなのか。
10.4. For-Loops
for (s) yield e
だと値を返す (map) けれど、値がいらないとき (foreach) は
for (s) e
と書けばいいよ。
10.5. Generalizing For
for 内包表記は上記の変換規則に従うだけなので、map 、flatMap 、filter を提供するオブジェクトなら List 以外にも使えるよ。データベースのインターフェイスや XML tree なんかに使ってみてね。
ただし！ map と flatMap と filter の型が適切でない場合、for 内包表記の変換結果が well-typed じゃなくなることがあるから気をつけてね、とのこと。
def map[B](f: A => B): C[B] def flatMap[B](f: A => C[B]): C[B] def filter(p: A => Boolean): C[A]
という型にすればいいらしい。その後、「このインターフェイスを定義した trait を用意して、その trait を継承してないと for 内包表記を使えないようにしたいよね。でもそれには Scala の型システムは弱すぎてダメなんだ」みたいなことが書いてあった。
まあ well-typed にならなくても型チェッカで検出してくれるからいいと思うんだけど、何か問題かな。map だけ提供する e だと、for (x <- e) は通るけど for (x <- e if f) は通らないのが嫌、両方通したくない、ということかな。
11. Mutable State
書き換え可能な変数の話。って今までちゃんと出てきてなかったのか。すげえ。
11.1. Stateful Objects
Scala で書き換え可能な状態は全部 var で作られる。
var x = "foo" x = "bar"
var は定義と同時に初期化もしないとダメ。var x: Int は怒られる。初期値を考えたくない場合は、以前出てきたデフォルト値の _ を使う。
var x : Int = _
マニュアルには誤植があって、var が val になってたからちょっと悩んだ。
状態のあるオブジェクトを作りたかったら var をメンバとして持たせる。3 章に出てきた感じ。
状態を入れると参照透過じゃなくなるよ。操作的等価性とは「x と y を呼び出す任意の操作列の結果と、その操作列中の y をすべて x に置き換えた操作列の結果が同じなら、x と y は等価」。例えば、状態を持つ BankAccount クラスに対して、
val x = new BankAccount; val y = new BankAccount x deposit 30; y withdraw 20 // 足りない x deposit 30; x withdraw 20 // 足りる
という風に結果が変わるから等価じゃない。
val x = new BankAccount; val y = x
なら等価だよ。代入を入れたら、簡約だけのモデルじゃ扱えない。
11.2. Imperative Control Structures
while や do-while は書けるよ。else のない if も書けるよ。return も書けるよ。
でもこいつらは利便性のためだけにあるんだ。だって Scala ではこれらを自分で定義できるから。
def whileLoop(condition: => Boolean)(command: => Unit) { if (condition) { command; whileLoop(condition)(command) } else () }
と書いてあるけど、return ってどう書くんだろう。break や continue はないらしい。
11.3. Extended Example: Discrete Event Simulation
回路のシミュレーションの例。なかなか気合入った例。でもスルー
11.4. Summary
pure functional な書き方と imperative な書き方は適材適所だよ！
12. Computing with Streams
Stream (遅延リスト) の話。
なんだかんだ言っても、基本的には functional な書き方の方がいいわけです。例えば、start から end までの素数の和を求めるプログラム。
def sumPrimes(start: Int, end: Int): Int = { var i = stgart var acc = 0 while (i < end) { if (isPrime(i)) acc += i i += 1 } acc }
def sumPrimes(start: Int, end: Int) =
sum(range(start, end) filter isPrime)
明らかに functional の方がいい。でも、一旦 start から end までのリストを作るので、効率はよくない。
そこで Stream 。List とほぼ互換のインターフェイスを持つけど、cons の 2 つ目の引数が遅延評価される。よって、
def sumPrimes(start: Int, end: Int) =
sum(Stream.range(start, end) filter isPrime)
とすることで、無駄なリストを作らないようにできる。
ただし、Stream に :: と ::: はない。理由はしょうもなくて、x :: xs が xs.::(x) の略記なので、xs を遅延することができないというもの。うーん、かっこ悪い。それぞれ Stream.cons(x, xs) と xs append ys を使えとのこと。
13. Iterators
Stream の imperative 版。外部イテレータだと思う。定義。
trait Iterator[+A] { def hasNext: Boolean def next: A ... }
見ればわかるとおりだけど、使い方。
val it = Iterator.range(1, 100) while (it.hasNext) { val x = it.next println(x * x) }
あと定義の仕方。0 ばかりの無限リスト。trait ってインスタンス化できるんだ。
val it = new Iterator[Int] { def hasNext = true def next = 0 }
13.1. Iterator Methods
Iterator には List や Stream を模倣するメソッドがいろいろ定義されている。append 、map 、flatMap 、foreach 、filter 、zip など。
de append[B >: A](that: Iterator[B]): Iterator[B] = new Iterator[B] { def hasNext = Iterator.this.hasNext || that.hasNext def next = if (Iterator.this.hasNext) Iterator.this.next else that.next }
filter だけは次の要素を保持しておかないといけないので、Iterator を継承した BufferedIterator を返す。
14. Lazy Values
lazy val foo = { println("foo"); 1 }
うおお。val の前に lazy をつけると、初期化を遅延できるみたい。インタプリタで実行してみると
scala> lazy val foo = { println("foo"); 1 }
foo
foo: Int = 1あれ？遅延されないじゃん。プログラムをファイルにしてやってみると
object t { def main(args: Array[String]) { lazy val x : Int = { println("foo"); 1 } println("before") println(x) println(x) } }
$ scalac t.scala && scala t before foo 1 1
おお、遅延されてる。あー、"foo: Int = 1" って表示をするために参照してしまったのか。
必要になるまでデータベースアクセスとか重い処理を遅延させられる、というメリットが書いてある。
他に、複数のモジュールからなるプログラムの初期化順序を制御するのにも使えるらしい。
class Symbol(val compiler: Compiler) { import compiler.types._ def Add = new Symbol("+", FunType(List(IntType, IntType), IntType)) def Sub = new Symbol("-", FunType(List(IntType, IntType), IntType)) class Symbol(name: String, tpe: Type) { override def toString = name + ": " + tpe } }
なんと、そこで import できるのか。
class Types(val compiler: Compiler) { import compiler.symtab._ abstract class Type case class FunType(args: List[Type], res: Type) extends Type case class NamedType(sym: Symbol) extends Type case object IntType extends Type }
Types も同様に。
class Compiler { val symtab = new Symbols(this) val types = new Types(this) }
とすると、new Symbol(this) の中で types が必要になって、でも types はまだ初期化されていないからランタイムエラーになる。そこで
class Compiler { lazy val symtab = new Symbols(this) lazy val types = new Types(this) }
とすれば解決。とのことなんだけど、lazy つけないでコンパイルしてみても、どうにもランタイムエラーが出ない。なんかよくわからん。
あと、lazy val なら定義の中で自分自身を再帰的に参照できる。
lazy val x : Int = 1 + x
15. Implicit Parameters and Conversinos
既存のライブラリをカスタマイズするとかに使える技。
implicit parameter
題材として、半群とモノイドを表すクラス。そして文字列のモノイドと整数のモノイド。
abstract class SemiGroup[A] { def add(x: A, y: A): A } abstract class Monoid[A] extends SemiGroup[A] { def unit: A } object stringMonoid extends Monoid[String] { def add(x: String, y: String) = x.concat(y) def unit = "" } object intMonoid extends Monoid[Int] { def add(x: Int, y: Int) = x + y def unit = 0 }
で、sum 関数を考える。
def sum[A](xs: List[A])(m: Monoid[A]): A = (m.unit /: xs)(m.add)
使い方はこう。
sum(List("a", "bc", "def"))(stringMonoid) sum(List(1, 2, 3))(intMonoid)
で、最初の引数の型からどのモノイドを与えるべきかはわかるのに、いちいち書くのがダサいよね。という導入。半群とかモノイドとか言われると、実際にどういう状況で必要になるかぴんと来ないわけだけど、まあ要するに、「String または Int を引数に受け取るメソッド」みたいのを定義したいときの話だな。
このためにはまず implicit キーワードを仮引数につける。
def sum[A](xs: List[A])(implicit m: Monoid[A]): A = (m.unit /: xs)(m.add)
implicit がつけられるのは一番最後の仮引数だけ。さらに、stringMonoid とかの定義にも implicit をつける。
implicit object stringMonoid extends Monoid[String] { def add(x: String, y: String) = x.concat(y) def unit = "" } implicit object intMonoid extends Monoid[Int] { def add(x: Int, y: Int) = x + y def unit = 0 }
以上が準備。
このとき、implicit 仮引数に対応する引数だけが省略されたメソッド呼び出しがあったとする。
sum(List(1, 2, 3))
このときコンパイラは、「このメソッド呼び出しのある場所から、prefix などなしで参照できる識別子の中で、implicit がつけられているもの」を探し出して、オーバーロードの要領でもっとも specific なものを選んで、それを勝手に与える。この sum の場合は、stringMonoid と intMonoid が見えていて、さらに sum の第一引数が List[Int] なので、intMonoid が採用される。
stringMonoid と stringMonoid2 があって、どっちも extends Monoid[String] だったらどうなるんだろうと思って試したところ、複数あって決まんねーぞ、とエラーになった。
scala> sum[String](List("a", "bc", "def"))
<console>:10: error: ambiguous implicit values:
both object stringMonoid2 in object $iw of type object stringMonoid2
and object stringMonoid in object $iw of type object stringMonoid
match expected type Monoid[String]
sum[String](List("a", "bc", "def"))なるほど。
implicit conversion
型 S が期待される文脈に型 T の式が書かれてて、継承関係とかでもない (型 T を型 S と見なせない) ときは、implicit conversion が探される。implicit parameter 同様に、その式のある箇所から「prefix などなしで参照できる識別子の中で、implicit がつけられているもの」を探して、その中で型 (T => S) と見なせるものを採用する。
implicit def int2ordered(x: Int): Ordered[Int] = new Ordered[Int] { def compare(y: Int): Int = if (x < y) -1 else if (x > y) 1 else 0 }
とかあったとする。
def foo(x: Ordered[Int]) = ... foo(1)
というように、型 Ordered[Int] が期待される文脈に型 Int の式 1 があったら、
foo(int2ordered(1))
という風に勝手に変換しちゃうぜ、という話っぽい。
あと、implicit conversion はメンバの選択にも適用されるらしい。つまり、E.x とあって E の型に x が無かったら、I(E).x となるような implicit comversion を探すそうな。
いやあ、自分の足を打ちぬけそうな機能ですね。
view bound
ジェネリクスの章で出てきた A <% B の話。
def sort[A <% Ordered[A]](xs: List[A]): List[A] = { if (xs.length <= 1) xs else { val pivot = xs(xs.length / 2) val left = xs filter (x => x < pivot) val mid = xs filter (x => x == pivot) val right = xs filter (x => x > pivot) sort(left) ::: mid ::: sort(right) } }
は、A 自体が比較できなくても、A から Ordered[A] への implicit conversion があればそれを使って比較してソートする関数。
view bound は implicit parameter の syntax sugar だそうで、以下のような implicit parameter の c (もちろん適当に fresh な変数) が追加されて、中で比較が必要なところで適宜 c が呼ばれる、みたいな。
def sort[A](xs: List[A])(implicit c: A => Ordered[A]): List[A] = { if (xs.length <= 1) xs else { val pivot = xs(xs.length / 2) val left = xs filter (x => c(x) < pivot) val mid = xs filter (x => x == pivot) val right = xs filter (x => c(x) > pivot) sort(left)(c) ::: mid ::: sort(right)(c) } }
以下余談。最初 x == pivot のところを c(x) == pivot にしてたら、なんか sort(List(3,2,1)) とかが List() になって、おっかしーなーと試行錯誤したところ、
(5 : Ordered[Int]) == 5 // false
となることに気づいた。trait Ordered の定義を見てみたら == はない。つまり == はルートクラスに定義された物理等価で、Ordered のインスタンスと Int のインスタンスを比較してるから false になるんだろう。
16. Hindley/Milner Type Inference
Mini-ML のインタプリタの題材を実演して見せる章。いまさらだけど、Scala って Java プログラマをだまして型付き関数型言語のファンにさせる計画なんだろうか。
内容は MinCaml の型推論で習った通りなのでスルー。以下は気になった点。
- sealed abstarct class Foo という定義ができるらしい。sealed クラスは「そのクラスが定義されている定義の列の外で、そのクラスを継承するサブクラスやデータコンストラクタを作ることができない」ようなクラスらしい。
sealed abstract class FooBar {} case class Foo(x: Int) extends FooBar {} case class Bar(x: Int) extends FooBar {} sealed abstract class Hoge {} case class Baz(x: Int) extends FooBar {}
とやったらエラーになるかなと思ったら、ならなかった。「定義の列の外」とは、別ファイルのことか。
- Subst が Function1[Type, Type] を継承してる理由がわからない。s(t) と書きたいだけなら apply を定義するだけでいいと思うんだけど。Function1 に関係する implicit conversion でも使ってるのかな。
- パターンマッチには @ が書ける。Haskell の @ と同じだろう。
17. Abstractions for Concurrency
最後の章。並行 (だっけ、並列だっけ)。
17.1. Signals and Monitors
AnyRef に以下のメソッドが定義されている。
def synchronized[A](e: => A): A def wait() def wait(msec: Long) def notify() def notifyAll()
同期のプリミティブすぎて synchronized 以外はどう使えばいいんだったか悩む。Java の Object かなにかにあるのと同じかな。
BoundedBuffer の定義と、それの使い方
class BoundedBuffer[A](N: Int) { var in = 0, out = 0, n = 0 val elems = new Array[A](N) def put(x: A) = synchronized { while (n >= N) wait() elems(in) = x ; in = (in + 1) % N ; n = n + 1 if (n == 1) notifyAll() } def get: A = synchronized { while (n == 0) wait() val x = elems(out) ; out = (out + 1) % N ; n = n 1 if (n == N 1) notifyAll() x } }
import scala.concurrent.ops._ ... val buf = new BoundedBuffer[String](10) spawn { while (true) { val s = produceString ; buf.put(s) } } spawn { while (true) { val s = buf.get ; consumeString(s) } }
concurrent.ops に定義されてる spawn の定義はこう。
def spawn(p: => Unit) { val t = new Thread() { override def run() = p } t.start() }
17.2. SyncVars
しんくろないずどなばりゅー
17.3. Futures
import scala.concurrent.ops._ ... val x = future(someLengthyComputation) anotherLengthyComputation val y = f(x()) + g(x())
future の引数は別のスレッドで計算される。x() が呼ばれた時、計算が終わっていたらすぐに結果を返し、計算が終わっていなかったら終わるまで待ってから結果を返す。
def future[A](p: => A): Unit => A = { val result = new SyncVar[A] fork { result.set(p) } (() => result.get) }
いやー、callee 側の遅延評価の指示は熱いなあ。でも、帰り値が遅延できないから Unit => A を返すことになってるところがもう一歩。直接 A を返す場合でも caller 側で lazy val x = future(someLengthyComputation) ってすればいいんだろうけど、これを callee 側で指示できれば最高だった。
