読者です 読者をやめる 読者になる 読者になる

新人SEの学習記録

14年度入社SEの学習記録用に始めたブログです。気づけば社会人3年目に突入。

学習記録:Scala関数型デザイン 第5章

関数型 プログラミング 学習記録 Scala

第5章:正格と遅延

遅延リストの例

ここでは,例としてストリームでの一連の変換を,遅延を使って一回の処理にまとめる方法を示す。

trait Stream[+A]
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

  // 複数要素からStreamを作成するための,可変長引数メソッド
  def apply[A](as: A*): Stream[A] =
    if (as.isEmpty) empty 
    else cons(as.head, apply(as.tail: _*))
}

Stream型はList型とよく似ているが,Consデータコンストラクタは明示的なサンクを受け取るようになっている。
明示的なサンクとして渡されるのは() => Aと() => Stream[A]で,
Streamを調査または走査するためには,先のif2でやったようにこれらのサンクを強制的に評価する必要がある。

例として,要求に応じてStreamの先頭を取り出す関数を見てみる。

  def headOption: Option[A] = this match {
    case Empty => None
    case Cons(h, t) => Some(h())  // h()を使ってサンクを強制的に評価
  }

h()を使った強制的な評価以外はListのものと同じように動作することがわかる。
Streamの「実際に要求された部分だけ評価する=Consの末尾を評価しない」機能がどのように役立つのか見ていく。

ストリームを記憶し,再計算を回避する

一般的には,Consノードの値が強制的に取得された時点でそれをキャッシュしておきたい。
そこで,スマートコンストラクタと呼ばれる,本物のコンストラクタとはシグネチャが少し異なるデータ型を生成する関数を使用する。
慣例では,対応するデータコンストラクタの1文字目を小文字にしたものをスマートコンストラクタとして使用する。

  // 空でないストリームを作成するためのスマートコンストラクタ
  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

consスマートコンストラクタでは,Consのhaidとtailに対する名前渡しの引数を記憶する。
これはよく使用されるパターンで,サンクの処理が実行されるのは強制的な評価が最初に行われたときだけになる。
それ以降は,キャッシュされた遅延値が返される。

emptyスマートコンストラクタは単にEmptyを返すが,アノテーションとしてStream[A]が指定されている。
型推論に関してはこの方が都合がよい場合がある。

Stream.apply関数は,これら2つのスマートコンストラクタがどのように使用されるかを示す。

  // 複数要素からStreamを作成するための,可変長引数メソッド
  def apply[A](as: A*): Stream[A] =
    if (as.isEmpty) empty 
    else cons(as.head, apply(as.tail: _*))

この場合も,consの引数がScalaによってサンクにまとめられるため,
Streamが強制的に評価されるまでas.headとapply(as.tail: _*)式は評価されない。

ストリームを検査するためのヘルパー関数

先に進む前に,ストリームの検査を容易にするヘルパー関数をいくつか記述してみる。

Exercise 5.1
  • StreamをListに変換し,それによりストリームを強制的に評価する関数を記述せよ。
  def toList: List[A] =	this match {
    case Cons(h, t) => h() :: t().toList
    case _ => List()
  }

case Empty => Noneみたいなことを書いてしまっていたが,「Cons以外 => 空のList」でOKだった。
上の方もcase Cons(h, t) => Cons(h(), t().List)みたいに書いてしまったが,
これは前の章で作った自作のConsを使ったListのときの書き方であって,標準ライブラリの書き方ではh :: tでOK。

使うと以下のようになる。

scala> val x: Stream[Int] = Stream(1,2,3)
x: Stream[Int] = Stream(1, ?)

scala> x.toList
res7: List[Int] = List(1, 2, 3)

解答を見ると,上の書き方は末尾再帰じゃないので大きなストリームではstack overflowになるとのこと。
そうならない書き方は以下。

  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
  }

末尾再帰にするためにStreamの先頭から順にListに追加していき,最後にreverseしている。
流れは以下のような感じ。

go(Stream(1,2,3), List()).reverse
go(Stream(2,3), List(1)).reverse
go(Stream(3), List(2,1)).reverse
go(Stream(), List(3,2,1)).reverse
List(3,2,1).reverse
List(1,2,3)

最後のreverseを無くすためには,bufferとして可変リストを使う必要がある。

  def toListFast: List[A] = {
    val buf = new collection.mutable.ListBuffer[A]
    @annotation.tailrec
    def go(s: Stream[A]): List[A] = s match {
      case Cons(h,t) =>
        buf += h()
        go(t())
      case _ => buf.toList
    }
    go(this)
  }
Exercise 5.2
  • Streamの先頭からn個の要素を取り出す/スキップする関数take(n)とdrop(n)を記述せよ。

Consかつn > 0なら,h()とt().take(n-1)をconsに入れて返す。
解答ではn > 1とn == 1のときを場合分けしていたけど,下の書き方の方がいいんじゃ・・・?
なお,REPLでloadできるようにするためobject holder{}でプログラムを囲んでいるので,
一部がholder.Stream.consみたいな書き方になっている。

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

dropも似たような感じで書けた。

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

holder.Stream.cons(h(), t())はよくよく考えたらthisでした。
解答ではnに負の値が入ったときなどもthisを返す仕様なのでもっと簡単に書けている。

  def drop(n: Int): Stream[A] = this match {
    case Cons(_, t) if n > 0 => t().drop(n - 1)
    case _ => this
  }
Exercise 5.3
  • Streamの先頭から指定された述語とマッチする要素をすべて取り出すtakeWhileを記述せよ。

今までと同じ感じで書けた。

  def takeWhile(p: A => Boolean): Stream[A] = this match {
    case Cons(h, t) if (p(h())) => holder.Stream.cons(h(), t().takeWhile(p))
    case Cons(h, t) => t().takeWhile(p)
    case _ => holder.Stream.empty
  }

今まではcase _でEmptyを返していたが,解答を見る限りemptyスマートコンストラクタを使った方が良さそう。
ただ,takeWhileの解答は上の3行目のcase Cons(h,t)にあたる行がなく,正しく動かない気がする(自分が間違ってるのか?)
なお,t().takeWhile(p)のような場合はドットを使わずt() takeWhile pと書くのがScala流とのこと。