Scalazに関して、わりとtypeclassについてばかり書いていた気がするので、たまにはデータ構造の話を。Scalazには、結構昔から(Scalaz6の頃から) EphemeralStream というデータ構造があります。
https://github.com/scalaz/scalaz/blob/v7.0.0-M7/core/src/main/scala/scalaz/EphemeralStream.scala
Ephemeral を辞書で引くと、「儚い、刹那的」という意味らしいです。現状7.0.0-M7のEphemeralStream本体のソースコードには、使い方の説明や、データ構造の特性などの説明が一切ありません！！！
しかし、一応package.scalaに一言だけ以下のような説明があります。
https://github.com/scalaz/scalaz/blob/v7.0.0-M7/core/src/main/scala/scalaz/package.scala#L58
A stream that holds weak references to its elements, and recomputes them if needed
訳すと
「要素を弱参照で保持しているStreamです。必要になったら、再計算されます」
という感じでしょうか。
この、再計算されるというのが面白いところで
- java.lang.ref.WeakReferenceを使っているので、いつ再計算されるのかわかりません！
- 必ず毎回再計算されるわけでもなく、メモ化されているかもしれないし、再計算されるかもしれないということです
- 「2回目に要素を辿ったときは、メモ化された値が返されるかもしれないけれど、3回目に辿った際には再計算されて値が返る」ということがありえます
- しかも、要素毎にそれぞれWeakReferenceで包んであるので、要素をたどっていった際に、「10番目の要素はメモ化された値が返るけど、20番目の要素は再計算されて返ってくる」ということもありえます
- 例えば、以下のようにunfoldで定義して、かつわざとその内部でprintlnで副作用を起こして、途中でSystem.gcを挟むと、メモ化されたり再計算されたりする様子が確認できます
scala> EphemeralStream.unfold(1,{i:Int => if(i < 10){println(i);Some(i,i+1)}else None }) 1 res26: scalaz.EphemeralStream[Int] = scalaz.EphemeralStreamFunctions$$anon$4@1cb94723 scala> res26.toList 2 3 4 5 6 7 8 9 res27: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9) scala> res26.toList res28: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9) scala> res26.toList res29: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9) scala> System.gc scala> res26.toList 2 3 4 5 6 7 8 9 res31: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9)
なので、作成する際、
- 計算するたびに副作用を生じさせたり
- 計算するたびに値が異なる
というような定義の仕方をするとおかしなことになるので、注意が必要です(unfoldやiterateなどで定義する場合)
その他の特性について、もうちょっと詳しく説明すると
- 全体としては、Scala標準のStreamやListと同じで、片方向のLinkedListです
- Scala標準のStreamと同じで、遅延Listです
- emptyEphemeralStream, cons, unfold, iterate, range, fromStream, apply と、作成するのにいくつか方法があります
- iterate, fromStream, unfoldなどで定義すれば、無限の長さにすることもできます
- implicit def toIterable[A](e: EphemeralStream[A]): Iterable[A]という関数が定義されていて、Scala標準のIterableに暗黙変換できます
Scala標準のStreamは、先頭の要素のポインタが参照されていれば、必ず一度計算されたその後ろのすべての要素をずっと保持(メモ化)します。
一方EphemeralStreamの場合は、いつの間にか保持されたものが消えている可能性があります。作者が
「EphemeralStreamには組み込みのメモリリークがないけれど、Scala標準のStreamにはある」 https://twitter.com/dibblego/status/286383570140921856
と言っていて面白かったです。本気で言っているのか、皮肉で冗談で言ってるのかわからないですが、個人的には
「EphemeralStreamのほうがすべての面で優れている」
のではなく、ある程度(使い分けることが可能なら)使い分けるものではないかなーとは思います。つまり
- メモリを食い過ぎたら、勝手にメモ化した要素を捨ててくれるので、メモリ使い過ぎない
ことが利点ですが、それがそのまま
- 再計算することがあり、そのコストがかかる
という欠点にもなります。あと、それぞれの要素毎に Option[WeakReference[V] ] を保持しているので、一要素あたりのメモリ使用率という意味では、あまり効率よくない気がします
実際にEphemeralStreamを使うべき場面、(Scala標準のStreamとの)使い分けは、色々とパフォーマンス計測してみないと自分もよくわからないです(誰かやってください)
あと、余談ですが、unfoldがカリー化されているほうが型推論効いて便利なのではないかと思ったので、pull requestしたらとりこまれました。*1
最後に、EphemeralStream作り方の例をちょっとだけ載せておきます。*2
$ screpl org.scalaz%scalaz-core_2.9.2%7.0.0-M7 Welcome to Scala version 2.9.2 (Java HotSpot(TM) 64-Bit Server VM, Java 1.7.0_09). Type in expressions to have them evaluated. Type :help for more information. scala> import scalaz._ import scalaz._ scala> EphemeralStream.emptyEphemeralStream[Int] res0: scalaz.EphemeralStream[Int] = scalaz.EphemeralStreamFunctions$$anon$5@4b1a5060 scala> EphemeralStream.cons(1,EphemeralStream.emptyEphemeralStream) res1: java.lang.Object with scalaz.EphemeralStream[Int] = scalaz.EphemeralStreamFunctions$$anon$4@25fb51fb scala> res1.toList res2: List[Int] = List(1) scala> EphemeralStream.unfold(1,{i:Int => Some(i,i+1)}) res4: scalaz.EphemeralStream[Int] = scalaz.EphemeralStreamFunctions$$anon$4@59bc0a11 scala> res4.take(10).toList res5: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) scala> EphemeralStream.iterate(1){_ * 2} res6: scalaz.EphemeralStream[Int] = scalaz.EphemeralStreamFunctions$$anon$4@3529a6d6 scala> res6.take(10).toList res7: List[Int] = List(2, 4, 8, 16, 32, 64, 128, 256, 512, 1024) scala> EphemeralStream.range(1,10) res8: scalaz.EphemeralStream[Int] = scalaz.EphemeralStreamFunctions$$anon$4@2ded32eb scala> res8.toList res9: List[Int] = List(1, 2, 3, 4, 5, 6, 7, 8, 9) scala> EphemeralStream(1,3,7) res10: scalaz.EphemeralStream[Int] = scalaz.EphemeralStreamFunctions$$anon$4@65c90ca scala> res10.toList res11: List[Int] = List(1, 3, 7)
