月別: 2015年5月

Scalaでストリームを実装する

scalaでは基本的に式は正格評価されます。 評価を遅らせたい場合は、サンク(thunk)と呼ばれる関数にしてあげることになります。 単純な例から見てみてみましょう。

このようにあるA型の値をサンクにしたい場合は () => A 型の関数にしてあげればよいです。 評価したくなったタイミングで関数にユニット () を渡してあげる形になります。

特に関数定義の際に引数の評価を遅らせたいことがあると思います。 以下のように数字を2倍する関数を定義できます。

この場合、呼び出し側と実装部分で () を付けるのが面倒なのですが、 x とだけ書けば良いように、便利な構文が用意されています 以下は上記の twice と同じ関数です。

非常に便利ですね?

そんなこんなでストリームを実装してみます。 簡単に以下のような感じになります。

Stream(1, 2) は以下のように作れます。toList でリスト化できます。

Streamは非正格評価なので、無限に続く数列なんかもつくれちゃいます。 ただし無限列を評価しようとして toList をすると当然ながらスタックオーバーフローが発生します。

@tailrec で末尾再帰チェック

末尾再帰を意図した関数には @scala.annotaition.tailrec を付けるとコンパイル時にチェックがかかるようになることを知りました。 またこのアノテーションによってIntelliJ IDEAも末尾再帰になっていないときに警告を出してくれます。

たとえば階乗を計算する関数は次のように書いてあげればよさそうです。

もし末尾再帰になっていないときは次のような挙動になります。

末尾再帰なコードはコンパイル後にwhileループに置き換えられるためにコールスタックを消費せずにすみます。 普段Scalaのコードを書くとき、全く意識していなかったので気を付けたいと思います。

なお、2015年5月現在の情報ではJavaのコードは末尾再帰にしてもしなくてもコンパイラが吐くバイトコードは変わらないそうです。 Stream APIでがんばりましょう。そのうち対応してくれるんじゃないでしょうか(遠い目)。