9. パーサコンビネータライブラリの実装

9.5

labelとscopeの違い

シグネチャは全く同じ。

p: Parser[A]が失敗したときに、

• label: スタックの先頭にエラーメッセージだけ組み込む
• scope: スタックの先頭にLocationとエラーメッセージをプッシュする

つまり...、

override def label[A](message: String)(p: Parser[A]): Parser[A] =
  s => p(s).mapError(_.label(message))

override def scope[A](message: String)(p: Parser[A]): Parser[A] =
  s => p(s).mapError(_.push(s, message))


case class ParseError(stack: MyList[(Location, String)]) {

  def push(location: Location, message: String): ParseError =
    copy(stack = (location, message) :: stack)

  def label[A](s: String): ParseError =
    ParseError(latestLocation.map((_, s)).toList)

  def latest: MyOption[(Location, String)] =
    stack.lastOption

  def latestLocation: MyOption[Location] =
    latest.map(_._1)
}

13. 外部作用とI/O

13.2

IO型の問題点

• スタックオーバーフロー (13.3で解決)
• 発生する副作用が不明瞭
• ノンブロッキングI/Oを実行するための仕組みが無い

13.3

• トランポリン化
• runをトランポリン(trampoline)と呼び、TailRec型はトランポリン化するための汎用的なデータ構造
• コルーチン

13.4

TailRecをIO型として利用する問題点

スタックオーバーフローの問題しかまだ解決できてない、下記の問題は未だに残ってる。

• 発生する副作用が不明瞭
• ノンブロッキングI/Oを実行するための仕組みが無い

exercise 13.2

どうして、Free[Function0, A]はrunTrampolineが必要になるのか。

• トランポリン再帰でスタックオーバーフローを避ける
• どこでスタックオーバーフローになってる？？？

リスト 13.20

implicit val function0Monad = new Monad[Function0] {

def unit[A](a: => A) = () => a

// f(a())でOKなはず
def flatMap[A,B](a: Function0[A])(f: A => Function0[B]) = () => f(a())()

}

13.7

• 1. ストリーミングI/Oは(巨大な)ループが必要になることが多い
• 2. 合成可能ではない
• IO型で実装したループは、特定の目的に特化してしまう

メモ

キーワード

14

14.1

lineGt40k_1

  def lineGt40k_1(filename: String): IO[Boolean] = IO {
    val src = Source.fromFile(filename)
    try {
      var count = 0
      val lines: Iterator[String] = src.getLines()
      while (count <= 40000 && lines.hasNext) {
        lines.next()
        count += 1
      }
      count > 40000
    } finally src.close()
  }

メリット

• 最大でも1行分のメモリしか必要としない
• 答えが分かった時点で終了する
  • 40,001回以上ループが回ることがない

デメリット

• アルゴリズムとI/Oが混在している
  • 合成の障害となる

lineGt40k_2

def lineGt40k_2(filename: String): IO[Boolean] =
  lines(filename).map(_.zipWithIndex.exists(_._2 + 1 >= 40000))

def lines(filename: String): IO[Stream[String]] = IO {
  val src = Source.fromFile(filename)
  src.getLines().toStream.append {
    src.close()
    Stream.empty
  }
}

メリット

• 合成的なスタイル
• I/Oとアルゴリズムが分離されているように見える

デメリット

• ストリーム全体を評価する必要がある
  • リソースが最後までクローズされない
    • existsなどを使うと、途中までしか評価されず、クローズされない

scala> (1 to 1000).toStream.append {
     |   println("tail")
     |   Stream.empty
     | }
res0: scala.collection.immutable.Stream[Any] = Stream(1, ?)

scala> res0.exists(_ == 5)
res1: Boolean = true

scala> res0.exists(_ == 1001)
tail
res2: Boolean = false