Scalaz(13)- Monad:Writer - some kind of logger


前述のいくつかの議論から,F[T]はFPにおける演算の表現形式であることが分かった.ここでF[]は高次タイプだけでなく、IO[T],Option[T]のような演算プロトコル(computation protocol)または演算モデルの良い点を表している.演算モデルは、演算値Tの演算方式を仕様している.一方、Monadは特殊なFP演算モデルM[A]であり、持続演算モードである.前後の2つの演算をflatMapをチェーンとして接続します.複数のflatMapが同時に作用することで、1つのプログラム実行チェーンを形成することができる.flatMap関数実装では、メンテナンス状態値(state value)、トレース記録(log)などの追加の役割を追加できます. 
前回の議論では,flatMap関数の実装過程で付加的な役割をどのように増大させるかを,Loggerの実装例を用いて示した.トレース機能(logging)で、F[T]演算構造にトレース記録(log)としてStringタイプ値を追加しました.本論ではまず,前編のLoggerの例をいくつかのlog型の要約を行い,新しいLogger構造を設計する.
case class Logger[LOG, A](log: LOG, value: A) {
	def map[B](f: A => B): Logger[LOG,B] = Logger(log, f(value))
	def flatMap[B](f: A => Logger[LOG,B])(implicit M: Monoid[LOG]): Logger[LOG,B] = {
		val nxLogger = f(value)
		Logger(log |+| nxLogger.log, nxLogger.value)
	}
	  
}

以上のLoggerはLOGタイプを要約した:Monoidインスタンスを持つタイプはすべて可能で、Monoid|+|操作記号をサポートすることができる.これはflatMap関数の実装から確認できる.
もちろん、for-comprehensionを使用するには、LoggerのMonadインスタンスを取得する必要があります.しかし、Loggerには2つのタイプパラメータLogger[LOG,A]があるため、type lambdaでLOGタイプを固定し、Monad演算をAタイプ値のみにする必要があります.
object Logger {
	implicit def toLogger[LOG](implicit M: Monoid[LOG]) = new Monad[({type L[x] = Logger[LOG,x]})#L] {
		def point[A](a: => A) = Logger(M.zero,a)
		def bind[A,B](la: Logger[LOG,A])(f: A => Logger[LOG,B]): Logger[LOG,B] = la flatMap f
	}
}

Monadの例ではfor-comprehensionを使用できます.
def enterInt(x: Int): Logger[String, Int] = Logger("Entered Int:"+x, x)
                                                  //> enterInt: (x: Int)Exercises.logger.Logger[String,Int]
def enterStr(x: String): Logger[String, String] = Logger("Entered String:"+x, x)
                                                  //> enterStr: (x: String)Exercises.logger.Logger[String,String]

for {
	a <- enterInt(3)
	b <- enterInt(4)
	c <- enterStr("Result:")
} yield c + (a * b).shows                         //> res0: Exercises.logger.Logger[String,String] = Logger(Entered Int:3Entered I
                                                  //| nt:4Entered String:Result:,Result:12)

しかし、各タイプに対して操作関数を定義しなければならないので、使いにくいです.任意のタイプの注入操作方法を使用できます.
final class LoggerOps[A](a: A) {
	def applyLog[LOG](log: LOG): Logger[LOG,A] = Logger(log,a)
}
implicit def toLoggerOps[A](a: A) = new LoggerOps[A](a)
                                                  //> toLoggerOps: [A](a: A)Exercises.logger.LoggerOps[A]

任意のタイプAに対してapplyLog法を注入した.
3.applyLog("Int three")                           //> res1: Exercises.logger.Logger[String,Int] = Logger(Int three,3)
"hi" applyLog "say hi"                            //> res2: Exercises.logger.Logger[String,String] = Logger(say hi,hi)
for {
	a <- 3 applyLog "Entered Int 3"
	b <- 4 applyLog "Entered Int 4"
	c <- "Result:" applyLog "Entered String 'Result'"
} yield c + (a * b).shows                         //> res3: Exercises.logger.Logger[String,String] = Logger(Entered Int 3Entered 
                                                  //| Int 4Entered String 'Result',Result:12)

aplyLogでこのように操作するのはずっと便利になりました.LOGは、Monoidインスタンスを持つ任意のタイプであることができるからである.Stringタイプに加えて、VectorまたはListのような高次タイプを使用することもできます.
for {
	a <- 3 applyLog Vector("Entered Int 3")
	b <- 4 applyLog Vector("Entered Int 4")
	c <- "Result:" applyLog Vector("Entered String 'Result'")
} yield c + (a * b).shows                         //> res4: Exercises.logger.Logger[scala.collection.immutable.Vector[String],Str
                                                  //| ing] = Logger(Vector(Entered Int 3, Entered Int 4, Entered String 'Result')
                                                  //| ,Result:12)

一般的には、Vectorの方が効率的であることを以下で確認します.
Aが任意のタイプである以上、Option[T]のような高次タイプはどうだろう.
for {
	oa <- 3.some applyLog Vector("Entered Some(3)")
	ob <- 4.some applyLog Vector("Entered Some(4)")
} yield ^(oa,ob){_ * _}                           //> res0: Exercises.logger.Logger[scala.collection.immutable.Vector[String],Opti
                                                  //| on[Int]] = Logger(Vector(Entered Some(3), Entered Some(4)),Some(12))

同じように使えます.注意oa,obはOptionタイプなので使用しなければなりません^(oa,ob){...}それらを結合します.
Loggerの典型的な応用を見てみましょう:gcd(greatest common denominator)アルゴリズムの例:
def gcd(x: Int, y: Int): Logger[Vector[String], Int] = {
	if (y == 0 ) for {
		_ <- x applyLog Vector("Finished at " + x)
	} yield x
	else
	  x applyLog Vector(x.shows + " mod " + y.shows + " = " + (x % y).shows) >>= {_ => gcd(y, x % y) }
	  
}                                                 //> gcd: (x: Int, y: Int)Exercises.logger.Logger[Vector[String],Int]
gcd(18,6)                                         //> res5: Exercises.logger.Logger[Vector[String],Int] = Logger(Vector(18 mod 6 
                                                  //| = 0, Finished at 6),6)
gcd(8,3)                                          //> res6: Exercises.logger.Logger[Vector[String],Int] = Logger(Vector(8 mod 3 =
                                                  //|  2, 3 mod 2 = 1, 2 mod 1 = 0, Finished at 1),1)

注記>>=シンボルの使用は、LoggerのMonadインスタンスの特性を示しています.
実際にscalarはWriterデータ構造を提供しています.これはWriterTタイプの特例です.
type Writer[+W, +A] = WriterT[Id, W, A]

WriterT:scalaz/WriterTを見てみましょう.scala
final case class WriterT[F[_], W, A](run: F[(W, A)]) { self =>
...

WriterTは、演算値Aの外に状態値Wを付加し、ペア値(paired value)を形成する.これは典型的なFP状態維持モードである.ただしWriterTのこれ(W,A)は演算モデルF[]内にある.これにより,より高いレベルの要約が実現され,この状態維持の演算に多層演算プロトコル(F[])の影響を及ぼす.Writer演算はWriter演算モードの特例であり,F[]の影響を必要とせずに演算値を直接計算するので,Id[A]=AのためWriterのF[]はIdを採用している.WriterTがflatMapによってステータスメンテナンスを実現する方法を見てみましょう:scalaz/WriterT.scala:
 def flatMap[B](f: A => WriterT[F, W, B])(implicit F: Bind[F], s: Semigroup[W]): WriterT[F, W, B] =
    flatMapF(f.andThen(_.run))

  def flatMapF[B](f: A => F[(W, B)])(implicit F: Bind[F], s: Semigroup[W]): WriterT[F, W, B] =
    writerT(F.bind(run){wa =>
      val z = f(wa._2)
      F.map(z)(wb => (s.append(wa._1, wb._1), wb._2))
    })

flatMapF関数で(W,A)のWをMonoid append操作した.
実際にWriterは,演算モデルF[A]内に状態値Wを1つ増やしてF(W,A)という形式を形成する付加的なデータ構造といえる.このWriter構造を構築するために任意のタイプAに注入方法を提供すると、任意のタイプの演算は、メンテナンス状態、loggingなどの演算中に追加の役割を果たすためにWriterを使用することができる.scalaz/syntax/WriterOpsを見てみましょう.scala:
package scalaz
package syntax

final class WriterOps[A](self: A) {
  def set[W](w: W): Writer[W, A] = WriterT.writer(w -> self)

  def tell: Writer[A, Unit] = WriterT.tell(self)
}

trait ToWriterOps {
  implicit def ToWriterOps[A](a: A) = new WriterOps(a)
}

ナチスは方法注入です.どのタイプAでもsetとtellを使用してWriterタイプを構築できます.
3 set Vector("Entered Int 3")                     //> res2: scalaz.Writer[scala.collection.immutable.Vector[String],Int] = WriterT
                                                  //| ((Vector(Entered Int 3),3))
"hi" set Vector("say hi")                         //> res3: scalaz.Writer[scala.collection.immutable.Vector[String],String] = Writ
                                                  //| erT((Vector(say hi),hi))
List(1,2,3) set Vector("list 123")                //> res4: scalaz.Writer[scala.collection.immutable.Vector[String],List[Int]] = W
                                                  //| riterT((Vector(list 123),List(1, 2, 3)))
3.some set List("some 3")                         //> res5: scalaz.Writer[List[String],Option[Int]] = WriterT((List(some 3),Some(3
                                                  //| )))
Vector("just say hi").tell                        //> res6: scalaz.Writer[scala.collection.immutable.Vector[String],Unit] = Writer
                                                  //| T((Vector(just say hi),()))

Writerで上のLoggerを演算する例:
for {
	a <- 3 set "Entered Int 3 "
	b <- 4 set "Entered Int 4 "
	c <- "Result:" set "Entered String 'Result'"
} yield c + (a * b).shows                         //> res7: scalaz.WriterT[scalaz.Id.Id,String,String] = WriterT((Entered Int 3 En
                                                  //| tered Int 4 Entered String 'Result',Result:12))

Aが上位タイプであればList[T]のように使えますか.
for {
 la <- List(1,2,3) set Vector("Entered List(1,2,3)")
 lb <- List(4,5) set Vector("Entered List(4,5)")
 lc <- List(6) set Vector("Entered List(6)")
} yield (la |@| lb |@| lc) {_ + _ + _}            //> res1: scalaz.WriterT[scalaz.Id.Id,scala.collection.immutable.Vector[String]
                                                  //| ,List[Int]] = WriterT((Vector(Entered List(1,2,3), Entered List(4,5), Enter
                                                  //| ed List(6)),List(11, 12, 12, 13, 13, 14)))

確かに大丈夫です.
そのgcdの例は代表的で、Writerでgcd演算を演算し、追跡します.
def gcd(a: Int, b: Int): Writer[Vector[String],Int] =
  if (b == 0 ) for {
  	_ <- Vector("Finished at "+a.shows).tell
  } yield a
  else
   Vector(a.shows+" mod "+b.shows+" = "+(a % b).shows).tell >>= {_ => gcd(b,a % b)}
                                                  //> gcd: (a: Int, b: Int)scalaz.Writer[Vector[String],Int]

gcd(8,3)                                          //> res8: scalaz.Writer[Vector[String],Int] = WriterT((Vector(8 mod 3 = 2, 3 mo
                                                  //| d 2 = 1, 2 mod 1 = 0, Finished at 1),1))
gcd(16,4)                                         //> res9: scalaz.Writer[Vector[String],Int] = WriterT((Vector(16 mod 4 = 0, Fin
                                                  //| ished at 4),4))

トレース記録を維持する際にVectorを使用すると、Listよりも効率的になります.証明しましょう
def listLogCount(c: Int): Writer[List[String],Unit] = {
  @annotation.tailrec
  def countDown(c: Int, w: Writer[List[String],Unit]): Writer[List[String],Unit] = c match {
  	case 0 => w >>= {_ => List("0").tell }
  	case x => countDown(x-1, w >>= {_ => List(x.shows).tell })
  }
  val t0 = System.currentTimeMillis
  val r = countDown(c,List[String]().tell)
  val t1 = System.currentTimeMillis
  r >>= {_ => List((t1 -t0).shows+"msec").tell }
}                                                 //> listLogCount: (c: Int)scalaz.Writer[List[String],Unit]
def vectorLogCount(c: Int): Writer[Vector[String],Unit] = {
  @annotation.tailrec
  def countDown(c: Int, w: Writer[Vector[String],Unit]): Writer[Vector[String],Unit] = c match {
  	case 0 => w >>= {_ => Vector("0").tell }
  	case x => countDown(x-1, w >>= {_ => Vector(x.shows).tell })
  }
  val t0 = System.currentTimeMillis
  val r = countDown(c,Vector[String]().tell)
  val t1 = System.currentTimeMillis
  r >>= {_ => Vector((t1 -t0).shows+"msec").tell }
}                                                 //> vectorLogCount: (c: Int)scalaz.Writer[Vector[String],Unit]

(listLogCount(10000).run)._1.last                 //> res10: String = 361msec
(vectorLogCount(10000).run)._1.last               //> res11: String = 49msec

ほら、listLogCount(10000)は361 msecを使った
vectorLogCount(10000)は49 msecで、8、9倍速くなりましたね.