メリークリスマス！！！！！！
この記事は CAMPHOR- Advent Calendar 2015 の25日目の記事です.
Scala はまだ始めたばかりですがとりあえずジェネレータ作ったり遅延評価してみようと思います.
これまでの流れ
- Ruby の Enumerator でジェネレータを作ったり、遅延評価してみる - ryota-ka's blog
- Python でジェネレータを作ったり、遅延評価してみる - 意識低い開発者のBlog
- ECMAScript 6 でジェネレータを作ったり、遅延評価してみる - 意識低い開発者のBlog
- Rust でジェネレータを作ったり、遅延評価してみる - ryota-ka's blog
- Swift でジェネレータを作ったり、遅延評価してみる - 意識低い開発者のBlog
- PHP でジェネレータを作ったり遅延評価してみる - tanishiking log
ジェネレータ
とりあえず1から順番に無限に数字を生成するジェネレータを作ってみます.
Scalaではクロージャを使うことで割と簡単に実現することができます.
クロージャは評価可能な局所変数と評価する関数をまとめたもので、以上の例のように状態を保持する、関数を返す関数のようなものを定義することができます.
上の例の無名関数は実行されるたびに局所変数numの値を増やしてからnum:Intを返します.
遅延評価
クロージャを使ったジェネレータでも遅延評価が実現できていることが分かると思いますが、Stream を使うことによって遅延評価を簡単に実現することもできます.
まずは Stream の簡単な例を見てみましょう. Stream は List によく似ています.
Stream(1, ?) とはどういうことでしょうか？
Stream は先ほど述べたように List に似ているのですが、List の tail には残りの List へのポインタが入っているのに対して
Stream の tail には lazy val (? の正体) が入っています. lazy val はもちろん実際に計算に値が必要になるまで評価されることはないため、Streamの要素は遅延評価され無限の長さを持つことができます.
以下の例はStreamを使って同様のことを実現したものです.
range は Stream型を返すので以上のように再帰的に定義することができます.
フィボナッチ数列を無限に返すストリーム
それでは Stream を使って無限にフィボナッチ数を返すストリームを作ってみましょう.
コードは以下のような感じになります.
何故これが無限にフィボナッチ数を返すストリームになるかを解説していきます.
以下のような表を見てみると分かりやすいかもしれません.
これはfibGen や fibGen.tail などの Stream を正格コレクションに直した場合の数字列です.
| 1 | 2 | 3 | 4 | 5 | # |
|---|---|---|---|---|---|
| 1 | 1 | 2 | 3 | 5 | fibGen.tail |
| 0 | 1 | 1 | 2 | 3 | fibGen |
| (0,1) | (1,1) | (1,2) | (2,3) | (3,5) | fibGen.zip(fibGen.tail) |
| 1 | 2 | 3 | 5 | 8 | fibGen.zip(fibGen.tail).map(n => n._1 + n._2) |
このようにfibGenをひとつシフトしてその和を足せば 残りのストリームを定義することができます.
追記
View
scala にはコレクションを仮想的に遅延評価するためにビューという機能があります.
Stream以外のコレクションはすべて正格評価されるのですが、任意のコレクションをビューという遅延評価される仮想的なコレクションに変換し、forceメソッドで正格評価されるコレクションに戻すことができます.
例えば以下のような感じです
Stream と違って無限リストを生成することは出来ませんが、異常に巨大なコレクションの一部のみを取得したい場合などは気軽に遅延評価をすることができて便利だと思います. 詳しくは Collections - ビュー - Scala Documentation を参照お願いします
CAMPHOR- Advent Calendar は延長します！！！
明日は@ryota-kaです. お楽しみに！
