Scala Lazy!（Scala関数型デザインより）

「Scala関数型デザイン&プログラミング」の「第 5 章　正格と遅延」

ストリームによる、Lazy処理を行う。

コード

package example.laziness

import Stream._

trait Stream[+A] {
  def toListRecursive: List[A] = this match {
    case Cons(h,t) => h() :: t().toListRecursive
    case _ => List()
  }

  def toList: List[A] = {
    @annotation.tailrec
    def go(s: Stream[A], acc: List[A]): List[A] = s match {
      case Cons(h,t) => go(t(), h() :: acc)
      case _ => acc
    }
    go(this, List()).reverse
  }

  def take(n: Int): Stream[A] = this match {
    case Cons(h, t) if n > 1 => cons(h(), t().take(n - 1))
    case Cons(h, _) if n == 1 => cons(h(), empty)
    case _ => empty
  }

  @annotation.tailrec
  final def drop(n: Int): Stream[A] = this match {
    case Cons(_, t) if n > 0 => t().drop(n - 1)
    case _ => this
  }

  // (A, => B) は、(A,B)と同じようではあるが、遅延実行させるため
  // 第2引数を名前渡しで受け取る
  // def foldRight[B](z: => B)(f: (A, B) => B): B = this match {
  def foldRight[B](z: => B)(f: (A, => B) => B): B = this match {
    case Cons(h,t) => f(h(), t().foldRight(z)(f))
    case _ => z
  }

  def exists(p: A => Boolean): Boolean =
    foldRight(false)((a, b) => p(a) || b)

  def forAll(f: A => Boolean): Boolean =
    foldRight(true)((a, b) => f(a) && b)

  def takeWhile(f: A => Boolean): Stream[A] =
    foldRight(empty[A])((h, t) =>
      {
        println(s"h:${h}")
        if (f(h)) cons(h,t)
        else empty
      }
    )

  def headOption: Option[A] =
    foldRight(None: Option[A])((h,_) =>
    {
      println(s"h:${h}")
      Some(h)
    })
}
case object Empty extends Stream[Nothing]
case class Cons[+A](h: () => A, t: () => Stream[A]) extends Stream[A]

object Stream {
  def cons[A](hd: => A, tl: => Stream[A]): Stream[A] = {
    lazy val head = hd
    lazy val tail = tl
    Cons(() => head, () => tail)
  }

  def empty[A]: Stream[A] = Empty

  def apply[A](as: A*): Stream[A] =
    if (as.isEmpty) empty
    else cons(as.head, apply(as.tail: _*))

  def main(args: Array[String]): Unit = {
    val sl = Stream(1,2,3,4)
    println(s"sl:${sl}")
    println(s"sl:${sl.toList}")

    val r = sl.foldRight(0)((a,b) => a + b)
    println(s"r:${r}")

    val tw = sl.takeWhile((a) => a < 4)
    // この段階では、先頭だけfetchされる
    println(s"tw:${tw}")
    // toListを呼び出すと全部fetchされる
    println(s"tw:${tw.toList}")

  }

}

Stream 定義

case class Cons[+A](h: () => A, t: () => Stream[A]) extends Stream[A]

object Stream {
  def cons[A](hd: => A, tl: => Stream[A]): Stream[A] = {
    lazy val head = hd
    lazy val tail = tl
    Cons(() => head, () => tail)
  }

Streamは、サンク「() => A」で、渡して、すぐに評価させないようにする。
lazyキーワードをつけて、head遅延評価しつつ、キャッシュさせるようにする。

foldRight

  // (A, => B) は、(A,B)と同じようではあるが、遅延実行させるため
  // 第2引数を名前渡しで受け取る
  // def foldRight[B](z: => B)(f: (A, B) => B): B = this match {
  def foldRight[B](z: => B)(f: (A, => B) => B): B = this match {
    case Cons(h,t) => f(h(), t().foldRight(z)(f))
    case _ => z
  }

foldRightのfの定義次第で、遅延実行されるようになる。

    val sl = Stream(1,2,3,4)
    val tw = sl.takeWhile((a) => a < 4)
    // この段階では、先頭だけfetchされる
    println(s"tw:${tw}")
    // toListを呼び出すと全部fetchされる
    println(s"tw:${tw.toList}")

即実行の場合の結果

def foldRightB(f: (A, B) => B): B = this match {

h:4
h:3
h:2
h:1
tw:Cons(example.laziness.Stream$$$Lambda$7/226170135@3b6eb2ec,example.laziness.Stream$$$Lambda$8/381707837@1e643faf)
tw:List(1, 2, 3)

takeWhileが呼ばれた段階で、全データが取られてしまう。

遅延実行の場合の結果

def foldRightB(f: (A, => B) => B): B = this match {

h:1
tw:Cons(example.laziness.Stream$$$Lambda$7/226170135@43a25848,example.laziness.Stream$$$Lambda$8/381707837@3ac3fd8b)
h:2
h:3
h:4
tw:List(1, 2, 3)

必要になった時（toListが呼ばれた時等）に、データを取る。

ORMフレームワークのlazy loadのようだ。

one more thing

  @annotation.tailrec
  final def drop(n: Int): Stream[A] = this match {
    case Cons(_, t) if n > 0 => t().drop(n - 1)
    case _ => this
  }

末尾再帰させるために、finalをつける。 scalaが末尾再帰を最適化するためには、再帰関数が、オーバーライドされる可能性のないメソッドであること。つまり、メソッドを定義するクラスが final かメソッド自体がfinal、あるいは private であることなためである。