yoichi/20150528_fpinscala.md

## 20150528_fpinscala.md

      
    Raw
  

              20150528_fpinscala.md
            
          
    fpinscala読書会#8

Contents

5.4 Infinite streams and corecursion

前回の補足

import しておけば、定義より手前で使う時に Stream.cons のように書かなくて済む。
package fpinscala.laziness

import Stream._
sealed trait Stream[+A] {
  def map[B](f: A => B): Stream[B] = this match {
    case Cons(h, t) => cons(f(h()), t().map(f))
    case Empty => empty
  }
}

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: _*))
}

ones

無限のStream登場
object Stream {
  val ones: Stream[Int] = cons(1, ones)
}

scala> ones
res0: fpinscala.laziness.Stream[Int] = Cons(<function0>,<function0>)

scala> ones.take(3)
res1: fpinscala.laziness.Stream[Int] = Cons(<function0>,<function0>)

scala> ones.take(3).toList
res2: List[Int] = List(1, 1, 1)

scala> ones.toList
java.lang.OutOfMemoryError: GC overhead limit exceeded
  at scala.collection.immutable.List.$colon$colon(List.scala:112)
  at fpinscala.laziness.Stream$class.go$1(stream.scala:14)
  at fpinscala.laziness.Stream$class.toList(stream.scala:17)
  at fpinscala.laziness.Cons.toList(stream.scala:43)
  ... 28 elided

無限のStreamの計算でも、次のいずれかにあてはまるなら返ってくる。

thunk (unevaluated form of an expression)
有限個で答えが出る場合

scala> ones.map(_ + 1).exists(_ % 2 == 0)
res0: Boolean = true

scala> ones.takeWhile(_ == 1)
res1: fpinscala.laziness.Stream[Int] = Cons(<function0>,<function0>)

scala> ones.forAll(_ != 1)
res2: Boolean = false

そうでない場合は、
scala> ones.map(_ + 1).exists(_ == 1)
java.lang.StackOverflowError
        at scala.runtime.ObjectRef.zero(ObjectRef.java:23)
        at fpinscala.laziness.Stream$.cons(stream.scala)
        at fpinscala.laziness.Stream$class.map(stream.scala:41)
        at fpinscala.laziness.Cons.map(stream.scala:64)
        at fpinscala.laziness.Stream$$anonfun$map$2.apply(stream.scala:41)
        at fpinscala.laziness.Stream$$anonfun$map$2.apply(stream.scala:41)
        at fpinscala.laziness.Stream$.tail$lzycompute$1(stream.scala:69)
        at fpinscala.laziness.Stream$.fpinscala$laziness$Stream$$tail$1(stream.scala:69)
        at fpinscala.laziness.Stream$$anonfun$cons$2.apply(stream.scala:70)
        at fpinscala.laziness.Stream$$anonfun$cons$2.apply(stream.scala:70)
        at fpinscala.laziness.Stream$class.exists(stream.scala:53)
        at fpinscala.laziness.Cons.exists(stream.scala:64)
        ...

無限Streamの例

constant (EXERCISE 5.8)

ones の拡張で、一定値を無限に繰り返す
scala> constant(1).take(3).toList
res0: List[Int] = List(1, 1, 1)

scala> constant("hoge").take(3).toList
res1: List[String] = List(hoge, hoge, hoge)

scala> constant((1,2,3)).take(3).toList
res2: List[(Int, Int, Int)] = List((1,2,3), (1,2,3), (1,2,3))

定義
object Stream {
  def constant[A](a: A): Stream[A] = {
    cons(a, constant(a))
  }
}

from (EXERCISE 5.9)

nから始まる整数列
scala> from(0).take(5).toList
res0: List[Int] = List(0, 1, 2, 3, 4)

定義
object Stream {
  def from(n: Int): Stream[Int] = {
    cons(n, from(n+1))
  }
}

(おまけ) Pythonだと generator を使うと似たものが書ける。
from itertools import islice

def _from(n):
    while True:
        yield n
        n += 1

print(list(islice(_from(0), 0, 5)))
print(list(islice(map(lambda x: x + 1, _from(0)), 0, 5)))

fibs (EXERCISE 5.10)

おなじみのフィボナッチ列
scala> fibs.take(7).toList
res0: List[Int] = List(0, 1, 1, 2, 3, 5, 8)
scala> fibs.take(48).drop(46).toList
res1: List[Int] = List(1836311903, -1323752223)

定義
object Stream {
  val fibs: Stream[Int] = {
    def go(p: Int, q: Int): Stream[Int] = {
      cons(p, go(q, p+q))
    }
    go(0, 1)
  }
}

unfold

次のようなシグネチャを持つStream構築関数を考える
def unfold[A, S](z: S)(f: S => Option[(A, S)]): Stream[A]


z ... 初期状態
f ... 状態をとり、値と次の状態のペアを返す。
Option なのは有限打ち切りを表現するため

unfold みたいな関数を corecursive function と呼ぶ。

cf. recursive function は小さな方に行ってとまる。
止まらないことを Stream で表現してる。
次の章で出てくる状態の話とも関連: 状態 => (値, 次の状態)

定義 (EXERCISE 5.11)
object Stream {
  def unfold[A, S](z: S)(f: S => Option[(A, S)]): Stream[A] = f(z) match {
    case Some((a, s)) => cons(a, unfold(s)(f))
    case None => empty
  }
}

使用例  (EXERCISE 5.12)
fibs

文法（タプルの扱い方）がわからなかったので当てずっぽうで書いてみた：
object Stream {
  def fibs_unfold: Stream[Int] = {
    unfold((0, 1))((p, q) => Some(p, (q, p+q)))
  }
}

コンパイルエラー（エラーメッセージが役に立つこともある例！）
% scalac stream.scala
stream.scala:100: error: missing parameter type
Note: The expected type requires a one-argument function accepting a 2-Tuple.
      Consider a pattern matching anonymous function, `{ case (p, q) =>  ... }`
    unfold((0, 1))((p, q) => Some(p, (q, p+q)))
                    ^
stream.scala:100: error: missing parameter type
    unfold((0, 1))((p, q) => Some(p, (q, p+q)))
                       ^
two errors found

修正版
object Stream {
  def fibs_unfold: Stream[Int] = {
    unfold((0, 1))({case (p, q) => Some(p, (q, p+q))})
  }
}

scala> fibs_unfold.take(7).toList
res0: List[Int] = List(0, 1, 1, 2, 3, 5, 8)

scala> fibs.take(48).drop(46).toList
res1: List[Int] = List(1836311903, -1323752223)

from

object Stream {
  def from_unfold(n: Int): Stream[Int] = {
    unfold(n)(n => Some(n, n+1))
  }
}

scala> from_unfold(0).take(5).toList
res0: List[Int] = List(0, 1, 2, 3, 4)

constant

object Stream {
  def constant_unfold[A](a: A): Stream[A] = {
    unfold(a)(a => Some((a, a)))
  }
}

scala> constant_unfold(1).take(3).toList
res0: List[Int] = List(1, 1, 1)

ones は上記で出来てしまっているので skip
もっとunfold (EXERCISE 5.13)

map

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

scala> from(0).map_unfold(_ + 1).take(5).toList
res1: List[Int] = List(1, 2, 3, 4, 5)

take

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

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

scala> from_unfold(0).take_unfold(5).toList
res0: List[Int] = List(0, 1, 2, 3, 4)

takeWhile

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

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

scala> Stream(1,2,3).takeWhile_unfold(_ < 3).toList
res0: List[Int] = List(1, 2)

zipWith

sealed trait Stream[+A] {
  def zipWith_unfold[B,C](b: Stream[B])(f: (A, B) => C): Stream[C] =
    unfold((this, b))({
      case (Cons(ah, at), Cons(bh, bt)) => Some((f(ah(), bh()), (at(), bt())))
      case _ => None
    })
}

scala> from(1).zipWith_unfold(from(0))(_ - _).take(3).toList
res1: List[Int] = List(1, 1, 1)

zipAll

sealed trait Stream[+A] {
  def zipAll_unfold[B](s2: Stream[B]): Stream[(Option[A],Option[B])] =
    unfold((this, s2))({
      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 (Empty, Empty) => None
    })
}

scala> Stream(1,2,3).zipAll_unfold(Stream(11,12,13,14)).toList
res0: List[(Option[Int], Option[Int])] = List((Some(1),Some(11)), (Some(2),Some(12)), (Some(3),Some(13)), (None,Some(14)))

最後のEXERCISE

startsWith (EXERCISE 5.14)

Streamは無限にもなり得ることに注意 (take して一致確認というのは駄目)
駄目な例
sealed trait Stream[+A] {
  def startsWith[A](s2: Stream[A]): Boolean =
    this.zipAll_unfold(s2).forAll({
      case (Some(_), None) => true
      case (Some(h1), Some(h2)) => h1 == h2
      case (None, _) => false // (None, None) が網羅されてないという警告も防ぐ（実際はないけど）
    })
}  

scala> Stream(1,2,3) startsWith Stream(1,2)
res0: Boolean = true

scala> from(1) startsWith Stream(1,2)
java.lang.StackOverflowError
        at scala.runtime.VolatileByteRef.<init>(VolatileByteRef.java:18)
        at scala.runtime.VolatileByteRef.create(VolatileByteRef.java:21)
        at fpinscala.laziness.Stream$.cons(stream.scala:115)
        at fpinscala.laziness.Stream$.from(stream.scala:132)
        at fpinscala.laziness.Stream$$anonfun$from$2.apply(stream.scala:132)
        at fpinscala.laziness.Stream$$anonfun$from$2.apply(stream.scala:132)
        at fpinscala.laziness.Stream$.tail$lzycompute$1(stream.scala:117)
        at fpinscala.laziness.Stream$.fpinscala$laziness$Stream$$tail$1(stream.scala:117)
        at fpinscala.laziness.Stream$$anonfun$cons$2.apply(stream.scala:118)
        at fpinscala.laziness.Stream$$anonfun$cons$2.apply(stream.scala:118)
        at fpinscala.laziness.Stream$$anonfun$zipAll_unfold$1.apply(stream.scala:96)
        at fpinscala.laziness.Stream$$anonfun$zipAll_unfold$1.apply(stream.scala:94)
        at fpinscala.laziness.Stream$.unfold(stream.scala:142)
        ...

修正版
sealed trait Stream[+A] {
  def startsWith[A](s2: Stream[A]): Boolean =
    unfold(this.zipAll_unfold(s2).takeWhile(_._2 != None))({
      case Cons(h, t) => Some((h()._1 == h()._2, t()))
      case _ => None
    }).forAll(_ == true)
}

scala> Stream(1,2,3) startsWith Stream(1,2)
res0: Boolean = true

scala> from(1) startsWith Stream(1,2)
res1: Boolean = true

scala> from(1) startsWith ones
res2: Boolean = false

tails (EXERCISE 5.15)

sealed trait Stream[+A] {
  def tails: Stream[Stream[A]] =
    cons(this, unfold(this)({
      case Empty => None
      case Cons(_, t) => Some((t(), t()))
    }))
}

scala> Stream(1,2,3).tails.map(_.toList).toList
res0: List[List[Int]] = List(List(1, 2, 3), List(2, 3), List(3), List())

hasSubsequence

sealed trait Stream[+A] {
  def hasSubsequence[A](s: Stream[A]): Boolean =
    tails exists (_ startsWith s)
}

scala> from(1) hasSubsequence from(2).take(3)
res0: Boolean = true

scanRight (EXERCISE 5.16)

tails の一般化(?)
scala> Stream(1,2,3).scanRight(0)(_ + _).toList
res0: List[Int] = List(6,5,3,0)
// List(1+2+3+0, 2+3+0, 3+0, 0)

sealed trait Stream[+A] {
  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 scanRight[B](z: => B)(f: (A, => B) => B): Stream[B] =
    this.tails.map_unfold(_.foldRight(z)(f))
}

畳み込み結果の再利用ができていない。
scala> Stream(1,2,3).scanRight(0)((a, b) => {println("!");a + b}).toList
!
!
!
!
!
!
res0: List[Int] = List(6, 5, 3, 0)

わからないので答えを見ました。
sealed trait Stream[+A] {
  def scanRight[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
}

scala> Stream(1,2,3).scanRight(0)((a, b) => {println("!");a + b}).toList
!
!
!
res0: List[Int] = List(6, 5, 3, 0)

なお、同じことを無限リストに適用するとあふれます。
scala> from(1).scanRight(0)(_ + _)
java.lang.StackOverflowError
        at scala.runtime.AbstractFunction0$mcI$sp.<init>(AbstractFunction0.scala:12)
        at fpinscala.laziness.Stream$$anonfun$from$1.<init>(stream.scala:155)
        at fpinscala.laziness.Stream$.from(stream.scala:155)
        at fpinscala.laziness.Stream$$anonfun$from$2.apply(stream.scala:155)
        at fpinscala.laziness.Stream$$anonfun$from$2.apply(stream.scala:155)
        at fpinscala.laziness.Stream$.tail$lzycompute$1(stream.scala:140)
        at fpinscala.laziness.Stream$.fpinscala$laziness$Stream$$tail$1(stream.scala:140)
        at fpinscala.laziness.Stream$$anonfun$cons$2.apply(stream.scala:141)
        at fpinscala.laziness.Stream$$anonfun$cons$2.apply(stream.scala:141)
        at fpinscala.laziness.Stream$$anonfun$foldRight$1.apply(stream.scala:116)
        at fpinscala.laziness.Stream$$anonfun$scanRight$2.p1$lzycompute$1(stream.scala:123)
        at fpinscala.laziness.Stream$$anonfun$scanRight$2.fpinscala$laziness$Stream$class$$anonfun$$p1$1(stream.scala:123)
        at fpinscala.laziness.Stream$$anonfun$scanRight$2$$anonfun$2.apply(stream.scala:124)
        at scala.Function0$class.apply$mcI$sp(Function0.scala:40)
        at scala.runtime.AbstractFunction0.apply$mcI$sp(AbstractFunction0.scala:12)
        ...

Q. 無限リストに適用してもちゃんと返ってくる例を作れる？
回答例
scala> from(1).scanRight(empty[Int])(cons(_,  _))
res0: fpinscala.laziness.Stream[fpinscala.laziness.Stream[Int]] = Cons(<function0>,<function0>)
scala> from(1).scanRight(empty[Int])(cons(_,  _)).map(_.take(3).toList).take(3).toList
res1: List[List[Int]] = List(List(1, 2, 3), List(2, 3, 4), List(3, 4, 5))

5章のまとめ


Stream を使うことで、必要になるまで評価を遅延させつつ、リスト的なものを扱える
無限要素の Stream も扱える便利な関数たちを学んだ
定義に foldRight が使われていることに注意。
同じ計算を何度もしないように配慮して書くのはコツが必要（私はまだつかめていません）