Writer データ型 

すごいHaskellたのしく学ぼう 曰く:

Maybe モナドが失敗の可能性という文脈付きの値を表し、リストモナドが非決定性が付いた値を表しているのに対し、Writer モナドは、もう1つの値がくっついた値を表し、付加された値はログのように振る舞います。

本に従って applyLog 関数を実装してみよう:

def isBigGang(x: Int): (Boolean, String) =
  (x > 9, "Compared gang size to 9.")

implicit class PairOps[A](pair: (A, String)) {
  def applyLog[B](f: A => (B, String)): (B, String) = {
    val (x, log) = pair
    val (y, newlog) = f(x)
    (y, log ++ newlog)
  }
}

(3, "Smallish gang.") applyLog isBigGang
// res0: (Boolean, String) = (false, "Smallish gang.Compared gang size to 9.")

メソッドの注入が implicit のユースケースとしては多いため、Scala 2.10 に implicit class という糖衣構文が登場して、クラスから強化クラスに昇進させるのが簡単になった。ログを Semigroup として一般化する:

import cats._, cats.syntax.all._

implicit class PairOps[A, B: Semigroup](pair: (A, B)) {
  def applyLog[C](f: A => (C, B)): (C, B) = {
    val (x, log) = pair
    val (y, newlog) = f(x)
    (y, log |+| newlog)
  }
}

Writer 

LYAHFGG:

値にモノイドのおまけを付けるには、タプルに入れるだけです。Writer w a 型の実体は、そんなタプルの newtype ラッパーにすぎず、定義はとてもシンプルです。

Cats でこれに対応するのは `Writer` だ:

type Writer[L, V] = WriterT[Id, L, V]
object Writer {
  def apply[L, V](l: L, v: V): WriterT[Id, L, V] = WriterT[Id, L, V]((l, v))

  def value[L:Monoid, V](v: V): Writer[L, V] = WriterT.value(v)

  def tell[L](l: L): Writer[L, Unit] = WriterT.tell(l)
}

Writer[L, V] は、WriterT[Id, L, V] の型エイリアスだ。

WriterT 

以下は `WriterT` を単純化したものだ:

final case class WriterT[F[_], L, V](run: F[(L, V)]) {
  def tell(l: L)(implicit functorF: Functor[F], semigroupL: Semigroup[L]): WriterT[F, L, V] =
    mapWritten(_ |+| l)

  def written(implicit functorF: Functor[F]): F[L] =
    functorF.map(run)(_._1)

  def value(implicit functorF: Functor[F]): F[V] =
    functorF.map(run)(_._2)

  def mapBoth[M, U](f: (L, V) => (M, U))(implicit functorF: Functor[F]): WriterT[F, M, U] =
    WriterT { functorF.map(run)(f.tupled) }

  def mapWritten[M](f: L => M)(implicit functorF: Functor[F]): WriterT[F, M, V] =
    mapBoth((l, v) => (f(l), v))
}

Writer の値はこのように作る:

import cats._, cats.data._, cats.syntax.all._

val w = Writer("Smallish gang.", 3)
// w: WriterT[Id, String, Int] = WriterT(run = ("Smallish gang.", 3))

val v = Writer.value[String, Int](3)
// v: Writer[String, Int] = WriterT(run = ("", 3))

val l = Writer.tell[String]("Log something")
// l: Writer[String, Unit] = WriterT(run = ("Log something", ()))

Writer データ型を実行するには run メソッドを呼ぶ:

w.run
// res2: (String, Int) = ("Smallish gang.", 3)

Writer に for 構文を使う 

LYAHFGG:

こうして Monad インスタンスができたので、Writer を do 記法で自由に扱えます。

def logNumber(x: Int): Writer[List[String], Int] =
  Writer(List("Got number: " + x.show), 3)

def multWithLog: Writer[List[String], Int] =
  for {
    a <- logNumber(3)
    b <- logNumber(5)
  } yield a * b

multWithLog.run
// res3: (List[String], Int) = (List("Got number: 3", "Got number: 5"), 9)

プログラムにログを追加する 

以下が例題の gcd だ:

def gcd(a: Int, b: Int): Writer[List[String], Int] = {
  if (b == 0) for {
      _ <- Writer.tell(List("Finished with " + a.show))
    } yield a
  else
    Writer.tell(List(s"${a.show} mod ${b.show} = ${(a % b).show}")) >>= { _ =>
      gcd(b, a % b)
    }
}

gcd(12, 16).run
// res4: (List[String], Int) = (
//   List("12 mod 16 = 12", "16 mod 12 = 4", "12 mod 4 = 0", "Finished with 4"),
//   4
// )

非効率な List の構築 

LYAHFGG:

Writer モナドを使うときは、使うモナドに気をつけてください。リストを使うととても遅くなる場合があるからです。リストは mappend に ++ を使っていますが、++ を使ってリストの最後にものを追加する操作は、そのリストがとても長いと遅くなってしまいます。

主なコレクションの性能特性をまとめた表があるので見てみよう。不変コレクションで目立っているのが全ての演算を実質定数でこなす Vector だ。Vector は分岐度が 32 の木構造で、構造共有を行うことで高速な更新を実現している。

Vector を使った gcd:

def gcd(a: Int, b: Int): Writer[Vector[String], Int] = {
  if (b == 0) for {
      _ <- Writer.tell(Vector("Finished with " + a.show))
    } yield a
  else
    Writer.tell(Vector(s"${a.show} mod ${b.show} = ${(a % b).show}")) >>= { _ =>
      gcd(b, a % b)
    }
}

gcd(12, 16).run
// res6: (Vector[String], Int) = (
//   Vector("12 mod 16 = 12", "16 mod 12 = 4", "12 mod 4 = 0", "Finished with 4"),
//   4
// )

性能の比較 

本のように性能を比較するマイクロベンチマークを書いてみよう:

def vectorFinalCountDown(x: Int): Writer[Vector[String], Unit] = {
  import annotation.tailrec
  @tailrec def doFinalCountDown(x: Int, w: Writer[Vector[String], Unit]): Writer[Vector[String], Unit] = x match {
    case 0 => w >>= { _ => Writer.tell(Vector("0")) }
    case x => doFinalCountDown(x - 1, w >>= { _ =>
      Writer.tell(Vector(x.show))
    })
  }
  val t0 = System.currentTimeMillis
  val r = doFinalCountDown(x, Writer.tell(Vector[String]()))
  val t1 = System.currentTimeMillis
  r >>= { _ => Writer.tell(Vector((t1 - t0).show + " msec")) }
}

def listFinalCountDown(x: Int): Writer[List[String], Unit] = {
  import annotation.tailrec
  @tailrec def doFinalCountDown(x: Int, w: Writer[List[String], Unit]): Writer[List[String], Unit] = x match {
    case 0 => w >>= { _ => Writer.tell(List("0")) }
    case x => doFinalCountDown(x - 1, w >>= { _ =>
      Writer.tell(List(x.show))
    })
  }
  val t0 = System.currentTimeMillis
  val r = doFinalCountDown(x, Writer.tell(List[String]()))
  val t1 = System.currentTimeMillis
  r >>= { _ => Writer.tell(List((t1 - t0).show + " msec")) }
}

僕のマシンの実行結果だとこうなった:

scala> vectorFinalCountDown(10000).run._1.last
res17: String = 6 msec

scala> listFinalCountDown(10000).run._1.last
res18: String = 630 msec

List が 100倍遅いことが分かる。