kmizuの日記

プログラミングや形式言語に関係のあることを書いたり書かなかったり。

Lazyなリストの作り方

Scalaで再帰的に定義する方法がわからん、という話。

Haskell

a = 0:[x+1 | x <- a]

と書けるのをScalaに持っていって

def a:List[Int] = 0::((for(i <- a) yield { i+1})  toList)

と書くと、定義はできるんだけど実行するとStackOverFlowErrorがでる。

http://d.hatena.ne.jp/E_Mattsan/20080823#1219475971

再帰的な定義の方法というより、遅延評価を行う方法に関する話ですね。
Scalaは、Haskellと違ってデフォルトで正格な評価(=遅延評価を行わない)なので、上記のようなコードだとaを評価しようとすると必ずaが再帰的に評価されてしまい、結果としてStackOverFlowErrorになります。

それを避けるためには、自分で遅延評価を行うための仕組みを用意してあげる必要がありますが、幸い、Scalaでは遅延評価されるリストを作るためのライブラリscala.Streamがありますので(型が違うので、正確にはListではないですけど)、これを使うことで上のHakellのコードをエミュレートすることができます:

val a: Stream[Int] = Stream.cons(0, for(i <- a) yield i + 1)
println(a take 10 toList) // --> List(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)

ちなみに、0,1, 2, ...,となる無限リストを作りたいだけなら、

val a: Stream[Int] = Stream.from(0)

でOKです。