Scala の内面を Haskell 化する話

Scala を使って Haskell 風の記述をしている例を時々見かけるけれど、徹頭徹尾 Haskell になっている例はあまり見掛けない。アプリケーションロジックだけ見れば同じなんだけれど、実際の内部動作は全然違っていたりする。そして、パフォーマンスが致命的に劣っていたりすると、悲しくてやりきれない気持ちになる。Scala は、本当は出来る子なんですと。

そこで、Haskell っぽい記述に耐えうる Scala Library を整備していこうと思う。

循環無限リストの整備

Haskell の無限リストのつもりで Scala の Stream を使うと、こんな落とし穴が待ち受けている。

例えば、無限リストの第1000000*1000番目が欲しいとき、Haskellならば、メモリ不足にはならないんだけれど、

Prelude> repeat 42 !! (1000000*1000)
42

Scala の Stream を普通に使うと、メモリ不足に陥る。

scala> Stream.continually(42)(1000000*100)
java.lang.OutOfMemoryError: Java heap space

そこで、メモリを食わない continually を実装してみた。

  def betterContinually[A](elem: => A): Stream[A] = {
    lazy val result: Stream[A] = Stream.cons(elem, result)
    result
  }

scala> betterContinually(42)
res1: Stream[Int] = Stream(42, ?)

scala> res1(1000000*100)
res2: Int = 42

ふむ、うまくいった。あとはPimp my libraryパターンで、Stream object のメソッドとして追加しておこう。

  implicit def equipRepeatWithStream(dummy: Stream.type) = new {
    def repeat[A](elem: => A): Stream[A] = {
      lazy val result: Stream[A] = Stream.cons(elem, result)
      result
    }
  }
  
  // 用例：
  // Stream.repeat(42)

2011-06-24 追記

上記の repeat コードは、当初は下記のように書いておりました。が、lazy val を用いたほうがスマートなので、本日修正しました。ご指摘くださいました okomok さんに感謝します。

    def repeat[A](elem: => A): Stream[A] = {
      object CircularReferenceMaker {
        val result: Stream[A] = Stream.cons(elem, result)
      }
      CircularReferenceMaker.result
    }

遅延評価 fold としての foldRight の整備

Haskell の foldr のつもりで、Scala collection の foldRight を使うと、さらなる落とし穴も待ち受けている。

基本的に、Haskell の foldr は無限リストに適応可能である。リストに適用される関数が余再帰ならば何の問題も起こさない。

しかし、scala の foldRight はそうではなく、どんな場合でも無限リストには適用不可能である。必ず落ちてしまう。正格評価をする以上、foldRight の最初の動作としては最終要素への移動以外にはありえないからだ。（もちろん、その移動の実装としては、本当に tail をたどって移動する collection もあれば、全要素を反転した Array を作るという実装の collection もある）

まず、Haskell の foldr が無限リストに適用可能な例を示す。foldr を使って map を定義するという例。

myMap :: (a -> b) -> ([a] -> [b])
myMap f = foldr ((:) . f) []

当たり前だけれど、有限要素のリストで正常動作するし、

Prelude> map (2*) [1..10]
[2,4,6,8,10,12,14,16,18,20]

無限要素のリストを渡しても正常動作する。

Prelude> take 10 (map (2*) [1..])
[2,4,6,8,10,12,14,16,18,20]

これをそのまま scala に書き直しても、

  // ダメな例
  def myMap[A, B](s: Stream[A], f: A => B): Stream[B] =
    s.foldRight[Stream[B]](Stream.Empty)((car, cdr) => Stream.cons(f(car), cdr))

有限要素の Stream には期待通りの動作をするが、

scala> myMap(Stream.range(1, 10), 2* : Int => Int) print
2, 4, 6, 8, 10, 12, 14, 16, 18, empty

無限要素になると、動作しない。

scala> myMap(Stream.from(1), 2* : Int => Int) take 10 print
Exception in thread "main" java.lang.StackOverflowError

そこで、遅延評価をする本物の fold として foldr を下記のように定義してあげる。

  def foldr[A, B](lseq: LinearSeq[A], f: (A, => B) => B, v: B): B =
    if (lseq.isEmpty) v
    else f(lseq.head, foldr(lseq.tail, f, v))

すると、有限要素はもとより無限要素の Stream に対しても、正常動作するようになる。

  def myMap2[A, B](s: Stream[A], f: A => B): Stream[B] = 
    foldr[A, Stream[B]](s, (car, cdr) => Stream.cons(f(car), cdr), Stream.Empty)

scala> myMap2(Stream.range(1, 10), 2* : Int => Int) print
2, 4, 6, 8, 10, 12, 14, 16, 18, empty

scala> myMap2(Stream.from(1), 2* : Int => Int) take 10 print
2, 4, 6, 8, 10, 12, 14, 16, 18, empty