正格と遅延

by bloody_snow

1 / 83

本章では、非正格性がどのようなものであるかを説明し、複数の変換を融合する遅延リスト型の実装を示します。
本章の目的は「ワンランク上の」リストを構築することですが、非正格性が一般的な関数型プログラムの効率性とモジュール性を向上させるための基本的な手法であることがわかるでしょう。

導入

List(1, 2, 3, 4).map(_ + 10).filter(_ % 2 == 0).map(_ * 3)

のような処理を実行すると

(1, 2, 3, 4) => (11, 12, 13, 14) => (12, 14) => (36, 42)

と中間のリストが都度生成されて無駄である。

List(1, 2, 3, 4).map(_ + 10).filter(_ % 2 == 0).map(_ * 3)
List(11, 12, 13, 14).filter(_ % 2 == 0).map(_ * 3)
List(12, 14).map(_ * 3)
List(36, 42)

var b = ArrayBuffer.empty[Int]
for(x <- List(1, 2, 3, 4)) {
  val y = x + 10
  if(y % 2 == 0) {
    b.append(y * 3)
  }
}

List(1, 2, 3, 4).collect {
  case x if (x + 10) % 2 == 0 => (x + 10) * 3
}

みたいなのはいけてない

for {
  x <- List(1, 2, 3, 4)
  y = x + 10
  if y % 2 == 0
} yield 
  y * 3

こうしたループの自動的な融合は、非正格性を使えば実現できます・・・！

5.1 正格関数と非正格関数

非正格性は関数の特性です。非正格性を持った関数は非正格関数と呼びます。

正格な評価

値呼び
参照呼び
Call by copy-restore
部分評価

値呼び

多くの言語で採用されている典型的な評価戦略である。値呼びでは、関数呼び出しにある実引数を評価し、関数の仮引数を新しい変数としてその値に束縛し、しかる後に関数本体を実行する。関数の中で仮引数である変数に値を代入しても、それは局所的なコピーへの代入であり、呼び出した側の変数には影響しない。

int a = 0;

int f(int a) {
  a += 100;
  return a;
}

a = f(a);

参照呼び

仮引数が実引数そのもの、すなわちエイリアスになる。実引数は、左辺値を持たねばならない（Pascalのように、実引数を変数に限定した言語もある）か、左辺値を持たない式の場合は呼び出し側で一時的オブジェクトを構築する言語もある。

int a = 0;

void f(int *a) {
  *a += 100;
}

f(&a);

Call by copy-restore

参照呼びの特殊な実装とも見ることができる。実引数の値が値呼びと同様にコピーされるが、関数呼び出しから戻る時に仮引数の変数の値が、あたかも参照呼びされたかのように書き戻される。

参照呼びと異なるのは、ある call by copy-restore の関数呼び出しの複数の引数に同じ変数を渡した場合、参照呼びでは、引数の1つを更新すると他の引数の内容も更新されるが、こちらでは、それぞれが異なるコピーであるため、他の引数の内容が更新されない。呼び出し側に戻ったときにどうなるかはそれぞれの仕様ないし実装による。

他にも、再帰呼び出しを行ったり、マルチスレッド環境で他のスレッドから観察されたりした場合には結果が異なってくる場合がある。

遠隔手続き呼出し (RPC) などで、このようなふるまいが見られることがある。

部分評価

適用されていない関数の本体内で評価が継続される。束縛されていない変数を含まない部分式は評価され、引数が既知の関数適用は簡約される。副作用があると、部分評価は予期しない結果を引き起こす可能性がある。このため、部分評価は関数内の副作用を持たない純粋な式についてのみ実施されることが多い。

ref 部分評価

正格でない評価

名前呼び
必要呼び
マクロ展開呼び

名前呼び

もっぱらプログラミング言語よりは計算模型で使われる用語で、最も外側の簡約可能な式を簡約する評価戦略であり、関数の引数を評価する前に関数を適用する。プログラミング言語における名前呼びに同じとされることも多いが、英語版Wikipediaでは、名前呼びでは適用されない関数の本体内までは評価しない点が異なるとしている。

ref 簡約律

def f(a: => Int): Int = {
  a + a
}

必要呼び

名前呼びをメモ化したようなもので、関数の引数が評価されると、その値がそれ以降の利用のために代替として格納される。副作用がない場合、これは名前呼びと同じ結果となる。引数が何度も使われている場合、（更新に要するコストの合計が毎回計算するコストの合計より小さければ）必要呼びの方が性能がよい。

遅延評価を引数の評価戦略として見た場合は必要呼びである、と言える。

必要呼びの言語としてはHaskellが有名である。

def f(a: => Int): Int = {
  lazy val b = a
  b + b
}

マクロ展開呼び

名前呼びと似ているが、捕獲回避置換ではなくテキスト置換を使う（ため、捕獲が起き得る）。マクロ展開呼びであることを意識せずに使っていると、予期しない結果になることがある。Hygienicマクロ（英語版）は、捕獲を回避するマクロである。

正格関数

引数が常に評価される関数

ほとんどのプログラミング言語の標準であり、それどころか、ほとんどの言語がサポートしているのは引数が完全に評価されることを期待する関数だけです。特に明記しない限り、Scalaの関数定義はすべて正格であると考えてください。

def square(x: Double): Double = x * x

square(41.0 + 1.0) => square(42.0) => 42.0 * 42.0

正格性の正式な定義

式の評価がいつまでも終了しない、あるいは明確な値を返さずにエラーをスローする場合を、式が終了しない、またはボトムに評価されると言います。
関数 f が正格となるのは、ボトムに評価されるすべての x に対して、式 f(x) がボトムに評価される場合です。

非性格関数

引数の1つ以上をすぐには評価しない状態(サンク)で受け取る関数

その引数の1つ以上を評価しないという選択が可能です。
たとえば、Scala をはじめとする多くのプログラミング言語には、短絡論理関数 && および || が含まれていますが、これらは非正格です。
&& と || については、言語に組み込まれている構文として考えることに慣れているかもしれませんが、引数を評価しないことを選択できる関数として考えることもできます。また、Scalaのif制御構造も同様です。

ref 正格と非正格（遅延）について

false && { println("!!"); true } // 後ろのprintlnは評価されない

true || { println("!!"); false } // 後ろのprintlnは評価されない

val result = if (input.isEmpty) sys.error("empty input") else input // inputがemptyじゃなければ前のerrorは評価されない

Scala で非正格関数を記述するには、引数の一部を評価されない状態で受け取ります。

非正格関数であるifの実装例

def if2[A](cond: Boolean, onTrue: () => A, onFalse: () => A): A =
  if (cond) onTrue() else onFalse()

if2(a < 22, () => println("a"), () => println("b"))

評価せずに渡したい引数の手前に() =>が付いていることがわかります。
() => A型の値は、0個の引数を受け取り、Aを返す関数です
評価されない形式の式を一般にサンク(thunk)と呼びます。
サンクに対しては、式の評価と結果の取得を強制することができます。
そのためには、onTrue()やonFalse()のように、関数を呼び出して空の引数リストを渡します。

全体的には、この構文により、何をしているのかが非常に明確になります。各非正格パラメータの代わりに引数なしの関数を渡した後、この関数を本体から明示的に呼び出して結果を取得しています。ただし、これは非常によくあるケースなので、より便利な構文が用意されています。

def if2[A](cond: Boolean, onTrue: => A, onFalse: => A): A = if (cond) onTrue else onFalse

通常の関数呼び出しの構文を使用するだけで、Scalaが式をサンクで囲んでくれます。

どちらの構文でも、評価されずに関数に渡される引数は、関数の本体内で参照されている場所ごとに1回だけ評価されます。つまり、Scala は引数の評価結果を(デフォルトでは)キャッシュしません。

キャッシュしない例

scala> def maybeTwice(b: Boolean, i: => Int) = if (b) i+i else 0
maybeTwice: (b: Boolean, i: => Int)Int
scala> val x = maybeTwice(true, { println("hi"); 1+41 })
hi
hi
x: Int = 84

キャッシュする例(lazyキーワードを使って値を明示的にキャッシュ)

scala> def maybeTwice2(b: Boolean, i: => Int) = { 
 lazy val j = i
 if (b) j+j else 0
}
maybeTwice: (b: Boolean, i: => Int)Int
scala> val x = maybeTwice2(true, { println("hi"); 1+41 })
hi
x: Int = 84

val 宣言にlazyキーワードを追加すると、そのlazy val宣言の右辺の評価が最初に参照されるときまで先送りされます。
また、その後の参照で評価を繰り返し行うことがないよう、結果がキャッシュされます。

なお、Scala の非正格関数は引数を値渡しではなく名前渡しで受け取ります。
Scala で関数を定義する際、仮引数名と型名の間に「 => 」を記載すると名前渡しとなり、値が必要になったときに式の値が評価されます。

【参考】
(評価戦略)https://ja.wikipedia.org/wiki/評価戦略[http://www.fos.kuis.kyoto-u.ac.jp/~igarashi/class/isle4-04w/text/eopl014.html]

5.2 遅延リストの例

ここでは、遅延リスト(ストリーム)を使用する関数型プログラムの効率性とモジュール性を向上させるために、遅延性をどのように利用できるかについて見ていきます。ここでは例として、ストリームでの一連の変換を、遅延を使って1回の処理にまとめる方法を示します。
ストリームはリスト 5-2 のように定義されています。ここでは新しい概念がいくつか登場するため、それらについても説明します。

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 

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

: _* is a special instance of type ascription which tells the compiler to treat a single argument of a sequence type as a variable argument sequence, i.e. varargs.

Stream型はList型とよく似ていますが、Consデータコンストラクタは通常の正格値ではなく明示的なサンクを受け取ります。

def headOption: Option[A] = this match {
  case Empty => None
  case Cons(h, t) => Some(h())
}

h()を使ってhを強制的に評価する必要があるものの、それ以外のコードはListのものと同じように動作することに注意してください。
実際に要求された部分だけを評価する(Consの末尾を評価しない)Streamの機能がどのように役立つのか見ていきましょう。

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

一般的には、Cons ノードの値が強制的に取得された時点で、それをキャッシュしておきたいところです。
たとえば、Consデータコンストラクタを直接呼び出した場合、以下のコードは expensive(x) を実際には2回計算します。

val x = Cons(() => expensive(x), tl) 
val h1 = x.headOption
val h2 = x.headOption

一般的には、スマートコンストラクタ(smart constructor)を定義することで、この問題を回避します。
スマートコンストラクタ(スマート構築子)とは、追加の不変条件を満たすデータ型、あるいはパターンマッチングに使用される「本物」のコンストラクタとはシグネチャが少し異なるデータ型を生成する関数のことです。
慣例では、対応するデータコンストラクタの1文字目を小文字にしたものをスマートコンストラクタとして使用します。
リスト5-2のconsスマートコンストラクタは、Consのheadとtailに対する名前渡しの引数を記憶します。
これはよく使用されるパターンであり、サンクの処理が実行されるのは、サンクの強制的な評価が最初に行われたときだけとなります。
それ以降は、キャッシュされた遅延値(lazy val)が返されます。

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

empty スマートコンストラクタは単に Empty を返しますが、Empty のアノテーションとして Stream[A] が指定されています。型推論に関しては、このほうが都合がよい場合があります。
Scalaでは、データコンストラクタを表すために部分型が使用されることを思い出そう。しかし、Stream については、Cons や Empty ではなく型として推論したい場合がほとんどである。このため、基底型(base type)(AnyValを継承したクラス)を返すスマートコンストラクタを作成するのが常套手段となっている。

Stream.apply 関数は、これら2つのスマートコンストラクタがどのように使用されるのかを示しています。

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: _*)式は評価されません。

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

先へ進む前に、ストリームの検査を容易にするヘルパー関数をいくつか記述してみましょう。

Exercise 5.1

trait Stream[+A] {
  def toList: List[A] = this match {
    case Cons(a, tail) => a() +: tail().toList
    case Empty => Nil
  }
}

property("toList") = forAll { l: List[Int] =>
  Stream.apply(l:_*).toList == l
}

def toListTailrec: List[A] = {
  @tailrec
  def go(s: Stream[A], l: List[A]): List[A] = s match {
    case Cons(a, tail) => go(tail(), a() +: l)
    case Empty => l
  }

  go(this, Nil).reverse
}

Exercise 5.2

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

implicit def arbStream[T](implicit a: Arbitrary[T]): Arbitrary[Stream[T]] = Arbitrary {
  Arbitrary.arbitrary[List[T]].map(ls => Stream.apply(ls: _*))
}

property("take") = forAll { (l: Stream[Int], i: Int) =>
  l.take(i).toList == l.toList.take(i)
}

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

Exercise 5.3

def takeWhile(p: A => Boolean): Stream[A] = this match {
  case Cons(a, tail) if p(a()) => cons(a(), tail().takeWhile(p))
  case _ => Empty
}

def createP(i: Int) = {
  val p = (x: Int) => x > i
  val q = (x: Int) => x < i
  val r = (x: Int) => if(i != 0) x % i == 0 else false
  Seq(p, q, r)
}

property("takeWhile") = forAll { (l: Stream[Int], i: Int) =>
  createP(i).forall(p => l.takeWhile(p).toList == l.toList.takeWhile(p))
}

5.3 プログラムの記述と評価の切り分け

関数型プログラミングの主なテーマの1つは関心の分離です。処理の記述(descrption)をそれらの実際の実行から切り離す必要があります。
遅延を利用することで、式の記述をその式の評価から切り離すことが可能になります。
それにより、必要以上に「大きな」式を表現し、その一部だけを評価できるようになります。これは強力な機能です。
例として、exists 関数を見てみましょう。この関数は、 Boolean 関数とマッチする要素がこの Stream に存在するかどうかをチェックします。

def exists(p: A => Boolean): Boolean = this match {
  case Cons(h, t) => p(h()) || t().exists(p)
  case _ => false
}

|| が第 2 引数に関して非正格であることに注目してください。p(h()) が true を返した場合、 exists は走査をそこで中断し、true を返します。また、ストリームの tail が lazy val で宣言されていることを思い出してください。つまり、走査が途中で終了するだけでなく、ストリームの末尾がまったく評価されないことになります。したがって、末尾を生成することになっていたはずのコードは、実際には実行されません。

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 exists2(p: A => Boolean): Boolean = foldRight(false)((a, b) => p(a) || b)

Exercise 5.4

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

property("forAll") = forAll { (l: Stream[Int], i: Int) =>
  createP(i).forall(p => l.forAll(p) == l.toList.forall(p))
}

Exercise 5.5

def takeWhile2(p: A => Boolean): Stream[A] = foldRight[Stream[A]](Empty)(
  (a, b) => if(p(a)) cons(a, b) else Empty
)

property("takeWhile2") = forAll { (l: Stream[Int], i: Int) =>
  createP(i).forall(p => l.takeWhile2(p).toList == l.toList.takeWhile(p))
}

Exercise 5.6

def headOption2: Option[A] = foldRight[Option[A]](None)(
  (a, b) => Some(a)
)

property("takeWhile2") = forAll { (l: Stream[Int], i: Int) =>
  createP(i).forall(p => l.takeWhile2(p).toList == l.toList.takeWhile(p))
}

Exercise 5.7

def map[B](f: A => B): Stream[B] = foldRight[Stream[B]](Empty)((a, b) =>
  cons(f(a), b)
)

property("map") = forAll { (l: Stream[Int], i: Int) =>
  createP(i).forall(p => l.map(p).toList == l.toList.map(p))
}

def filter(p: A => Boolean): Stream[A] = foldRight[Stream[A]](Empty)((a, b) =>
  if(p(a)) cons(a, b) else b
)

property("filter") = forAll { (l: Stream[Int], i: Int) =>
  createP(i).forall(p => l.filter(p).toList == l.toList.filter(p))
}

[B >: A] is a lower type bound. It means that B is constrained to be a supertype of A.

def append[B >: A](other: Stream[B]): Stream[B] = foldRight[Stream[B]](other)((a, b) =>
  cons(a, b)
)

property("append") = forAll { (l: Stream[Int], m: Stream[Int]) =>
  l.append(m).toList == l.toList ++ m.toList
}

def flatMap[B](f: A => Stream[B]): Stream[B] = foldRight[Stream[B]](Empty)((a, b) =>
  f(a).append(b)
)

property("flatMap") = forAll { (l: Stream[Int], a: Int, b: Int) =>
  val f = (x: Int) => Stream.apply(x, x * a, x * b)
  l.flatMap(f).toList == l.toList.flatMap(f andThen (_.toList))
}

本章で最初に示したStream(1,2,3,4).map(_ + 10).filter(_ % 2 == 0)という例の簡単なプログラムトレースを見てみましょう。これは完全なものではありませんが、この式を List に変換することでストリームを強制的に評価します。ここまでのトレースよりも少し複雑なので、このトレースにじっくり目を通して内容を理解してください。このようなトレースについては、同じ式が繰り返し評価され、そのつど評価ステップが1つ増えるだけであることを覚えておいてください。

Stream(1,2,3,4).map(_ + 10).filter(_ % 2 == 0).toList
(cons((_ + 10)(1), Stream(2, 3, 4).map(_ + 10)).filter(_ % 2 == 0).toList
cons(11, Stream(2,3,4).map(_ + 10)).filter(_ % 2 == 0).toList
Stream(2,3,4).map(_ + 10).filter(_ % 2 == 0).toList
cons(12, Stream(3,4).map(_ + 10)).filter(_ % 2 == 0).toList
12 :: Stream(3,4).map(_ + 10).filter(_ % 2 == 0).toList
12 :: cons(13, Stream(4).map(_ + 10)).filter(_ % 2 == 0).toList
12 :: Stream(4).map(_ + 10).filter(_ % 2 == 0).toList
12 :: cons(14, Empty.map(_ + 10)).filter(_ % 2 == 0).toList
12 :: 14 :: Empty.map(_ + 10).filter(_ % 2 == 0).toList 
12 :: 14 :: Nil

これは特殊なループを使ってロジックを差し挟むのとまったく同じです。ストリームが「ファーストクラスループ」と呼ばれることがあるのはこのためであり、そのロジックをmapやfilterといった高階関数を使って組み合わせることができます。

この変換では、mapによって11と13の値が出力され、それらの値にメモリ領域が割り当てられますが、これらの領域はfilterによって不要と判断された時点でガベージコレクト(メモリを解放)できます。もちろん、これは単純な例です。状況によっては、より多くの要素が必要になるかもしれませんし、ストリームの要素そのものがメモリを大量に確保する大きなオブジェクトの可能性もあります。このメモリをできるだけすみやかに回収できれば、プログラム全体で必要となるメモリ量を削減することが可能になります。

def find(p: A => Boolean): Option[A] = filter(p).headOption

と記述しても中間ストリームがインスタンス化されないので無駄な処理は起きない

5.4 無限ストリームと余再帰

val ones: Stream[Int] = Stream.cons(1, ones)

ones.take(5).toList // List(1, 1, 1, 1, 1)
ones.exists(_ % 2 != 0) // true

ones.map(_ + 1).exists(_ % 2 == 0) // true
ones.takeWhile(_ == 1) // Cons(() => 1, () => ones.takeWhile(_ == 1))
ones.forAll(_ != 1) // false

Exercise 5.8

def constant[A](a: A): Stream[A] = cons(a, constant(a))

type SmallInt = Int
implicit val smallIntArbitrary: Arbitrary[SmallInt] = Arbitrary(Gen.choose(0, 100))

property("constant") = forAll { (a: Int, b: SmallInt) =>
  constant(a).take(b).forAll(_ == a)
}

Exercise 5.9

def from(n: Int): Stream[Int] = cons(n, from(n + 1))

property("from") = forAll { (a: Int, b: SmallInt) =>
  from(a).take(b).toList == Range(a, a + b).toList
}

Exercise 5.10

def fibs(m: Int = 0, n: Int = 1): Stream[Int] = cons(m, fibs(n, m + n))

def fib(n: Int): Int = {
  @annotation.tailrec
  def go(n: Int, a: Int, b: Int): Int =
    if (n == 0) a
    else go(n - 1, b, a + b)

  go(n, 0, 1)
}

property("fibs") = forAll { n: SmallInt =>
  fibs().drop(n).headOption.get == fib(n)
}

Exercise 5.11

def unfold[A, S](z: S)(f: S => Option[(A, S)]): Stream[A] = f(z) match {
    case None => Empty
    case Some((a, s)) => cons(a, unfold(s)(f))
  }

unfold関数は、余再帰(corecursive)と呼ばれる関数の一例です。
再帰関数がデータを消費するのに対し、余再帰関数はデータを生成します。
また、再帰関数が再帰処理によって入力を小さくしていくことで終了するのに対し、余再帰関数は生産性が続く限り終了する必要がありません。
つまり、限られた時間の中で評価できる結果が常に増えていくのです。
関数fをもう一度実行するだけで Stream の次の要素を生成できるため、unfold関数の生産性はfが終了する限り維持されます。

https://github.com/fpinscala/fpinscala/wiki

Exercise 5.12

property("unfold") = forAll { (a: SmallInt, b: SmallInt, n: SmallInt) =>
  unfold(a)(s => Some((s, s + b))).drop(n).headOption.get == a + b * n
  ones.take(n).toList == unfold(a)(_ => Some((1, a))).take(n).toList
  constant(a).take(n).toList == unfold(b)(_ => Some(a, b)).take(n).toList
  from(a).take(n).toList == unfold(a)(x => Some((x, x + 1))).take(n).toList
  fibs().take(n).toList == unfold((0, 1))({ case (x, y) => Some(x, (y, x + y)) }).take(n).toList
}

Exercise 5.13

def map2[B](f: A => B): Stream[B] = unfold(this) {
  case Empty => None
  case Cons(h, t) => Some((f(h()), t()))
}

property("map2") = forAll { (l: Stream[Int], i: Int) =>
  createP(i).forall(p => l.map2(p).toList == l.toList.map(p))
}

def take2(n: Int): Stream[A] = unfold((this, n)) {
  case (Empty, _) => None
  case (_, n) if n <= 0 => None
  case (Cons(h, t), n) => Some((h(), (t(), n - 1)))
}

property("take2") = forAll { (l: Stream[Int], i: Int) =>
  l.take2(i).toList == l.toList.take(i)
}

def takeWhile3(p: A => Boolean): Stream[A] = unfold(this) {
  case Cons(h, t) if p(h()) => Some((h(), t()))
  case _ => None
}

property("takeWhile3") = forAll { (l: Stream[Int], i: Int) =>
  createP(i).forall(p => l.takeWhile3(p).toList == l.toList.takeWhile(p))
}

def zipWith[B](other: Stream[B]): Stream[(A, B)] = unfold((this, other)) {
  case (Cons(aH, aT), Cons(bH, bT)) => Some((aH(), bH()), (aT(), bT()))
  case _ => None
}

property("zipWith") = forAll { (l: Stream[Int], m: Stream[Int]) =>
  l.zipWith(m).toList == l.toList.zip(m.toList)
}

def zipAll[B](other: Stream[B]): Stream[(Option[A], Option[B])] = unfold((this, other)) {
  case (Cons(aH, aT), Cons(bH, bT)) => Some((Some(aH()), Some(bH())), (aT(), bT()))
  case (Cons(aH, aT), Empty) => Some((Some(aH()), None), (aT(), Empty))
  case (Empty, Cons(bH, bT)) => Some((None, Some(bH())), (Empty, bT()))
  case _ => None
}

property("zipAll") = forAll { (l: Stream[Int], m: Stream[Int]) =>
  l.zipAll(m).toList == l.toList.map(Some.apply).zipAll(m.toList.map(Some.apply), None, None)
}

Exercise 5.14

def startsWith[A](s: Stream[A]): Boolean = zipAll(s).forAll{
  case (Some(a), Some(b)) => a == b
  case (_, None) => true
  case (None, Some(_)) => false
}

property("startsWith") = forAll { (l: Stream[Int], m: Stream[Int], i: Int) =>
  l.startsWith(m) == l.toList.startsWith(m.toList)
}

Exercise 5.15

def tails: Stream[Stream[A]] = unfold(this)({
  case Empty => None
  case Cons(h, t) => Some(Cons(h, t), t())
}).append(Stream(Empty))

property("tails") = forAll { l: Stream[Int] =>
  l.tails.map(_.toList).toList == l.toList.tails.toList
}

Exercise 5.16

def scanRight[B](z: B)(f: (A, => B) => B): Stream[B] = tails.map { s =>
  s.foldRight(z)(f)
}

property("scanRight") = forAll { l: Stream[Int] =>
  l.scanRight(0)(_ + _).toList == l.toList.scanRight(0)(_ + _)
}

def scanRight2[B](z: B)(f: (A, => B) => B): Stream[B] = foldRight((z, Stream(z)))((a, p0) => {
  lazy val p1 = p0
  val b2 = f(a, p1._1)
  (b2, cons(b2, p1._2))
})._2

property("scanRight2") = forAll { l: Stream[Int] =>
  l.scanRight2(0)(_ + _).toList == l.toList.scanRight(0)(_ + _)
}

5.5 まとめ

正格性は、式の記述をその評価の方法やタイミングから切り離すことで、モジュール性を向上させることを目的としています。これらの関心を切り離しておくことで、同じ記述を複数のコンテキストで再利用することが可能となり、式の異なる部分を評価することで異なる結果が得られるようになります。正格コードのように記述と評価が結び付いている場合、このようなことは不可能です。