Traverse 

The Essence of the Iterator Pattern:

McBride と Paterson がアプリカティブ計算の動機として例に挙げた 3つの例のうち、 2つ (モナディックな作用のリストの sequence と、行列の転置) は traversal と呼ばれる一般スキームの例だ。 これは、map のようにデータ構造内の要素の反復することを伴うが、 ただし、ある特定の関数適用をアプリカティブに解釈する。

これは Traversable なデータ構造という型クラスとして表現される。

Cats では、この型クラスは Traverse と呼ばれる:

@typeclass trait Traverse[F[_]] extends Functor[F] with Foldable[F] { self =>

  /**
   * given a function which returns a G effect, thread this effect
   * through the running of this function on all the values in F,
   * returning an F[A] in a G context
   */
  def traverse[G[_]: Applicative, A, B](fa: F[A])(f: A => G[B]): G[F[B]]

  /**
   * thread all the G effects through the F structure to invert the
   * structure from F[G[_]] to G[F[_]]
   */
  def sequence[G[_]: Applicative, A](fga: F[G[A]]): G[F[A]] =
    traverse(fga)(ga => ga)
  ....
}

f が A => G[B] という形を取ることに注目してほしい。

m が恒等アプリカティブ・ファンクターであるとき、 traversal はリストのファンクター的な map と一致する (ラッパーを無視すると)。

Cats に恒等アプリカティブ・ファンクターは以下のように定義されている:

  type Id[A] = A
  implicit val Id: Bimonad[Id] =
    new Bimonad[Id] {
      def pure[A](a: A): A = a
      def extract[A](a: A): A = a
      def flatMap[A, B](a: A)(f: A => B): B = f(a)
      def coflatMap[A, B](a: A)(f: A => B): B = f(a)
      override def map[A, B](fa: A)(f: A => B): B = f(fa)
      override def ap[A, B](fa: A)(ff: A => B): B = ff(fa)
      override def flatten[A](ffa: A): A = ffa
      override def map2[A, B, Z](fa: A, fb: B)(f: (A, B) => Z): Z = f(fa, fb)
      override def lift[A, B](f: A => B): A => B = f
      override def imap[A, B](fa: A)(f: A => B)(fi: B => A): B = f(fa)
  }

Id を使って、List(1, 2, 3) を走査 (traverse) してみる。

scala> import cats._, cats.instances.all._
import cats._
import cats.instances.all._

scala> import cats.syntax.traverse._
import cats.syntax.traverse._

scala> List(1, 2, 3) traverse[Id, Int] { (x: Int) => x + 1 }
res0: cats.Id[List[Int]] = List(2, 3, 4)

モナディックなアプリカティブ・ファンクターの場合、traversal はモナディックな map に特化し、同じ用例となる。 traversal はモナディックな map を少し一般化したものだと考えることができる。

List を使って試してみる:

scala> List(1, 2, 3) traverse { (x: Int) => (Some(x + 1): Option[Int]) }
res1: Option[List[Int]] = Some(List(2, 3, 4))

scala> List(1, 2, 3) traverse { (x: Int) => None }
res2: Option[List[Nothing]] = None

Naperian なアプリカティブ・ファンクターの場合は、traversal は結果を転置する。

これはパス。

モノイダルなアプリカティブ・ファンクターの場合は、traversal は値を累積する。 reduce 関数は各要素に値を割り当てる関数を受け取って、累積する。

scala> import cats.data.Const
import cats.data.Const

scala> def reduce[A, B, F[_]](fa: F[A])(f: A => B)
         (implicit FF: Traverse[F], BB: Monoid[B]): B =
         {
           val g: A => Const[B, Unit] = { (a: A) => Const((f(a))) }
           val x = FF.traverse[Const[B, ?], A, Unit](fa)(g)
           x.getConst
         }
reduce: [A, B, F[_]](fa: F[A])(f: A => B)(implicit FF: cats.Traverse[F], implicit BB: cats.Monoid[B])B

これはこのように使う:

scala> reduce(List('a', 'b', 'c')) { c: Char => c.toInt }
res3: Int = 294

一応できたけど、型注釈を少し減らせるともっと良い感じがする。 問題は、現状の Scala 2.11 コンパイラは Const[B, ?] を推論できないことにある。 コンパイラを説得していくつかの形を推論させるテクニックがあって、これは Unapply と呼ばれている。 traverse の代わりに traverseU を使うとこれを利用できる:

scala> def reduce[A, B, F[_]](fa: F[A])(f: A => B)
         (implicit FF: Traverse[F], BB: Monoid[B]): B =
         {
           val x = fa traverseU { (a: A) => Const((f(a))) }
           x.getConst
         }
reduce: [A, B, F[_]](fa: F[A])(f: A => B)(implicit FF: cats.Traverse[F], implicit BB: cats.Monoid[B])B

これに関してはまた後で。

sequence 関数 

ApplicativeTraverse は McBride さんと Paterson さんによって Applicative programming with effects の中でセットで言及されている。

この背景として、数ヶ月前 (2015年3月) まで、Control.Monad パッケージの sequence 関数は以下のように定義されていた:

-- | Evaluate each action in the sequence from left to right,
-- and collect the results.
sequence :: Monad m => [m a] -> m [a]

これを Scala に翻訳すると、このようになる:

def sequence[G[_]: Monad, A](gas: List[G[A]]): G[List[A]]

これはモナディック値のリストを受け取って、リストのモナディック値を返す。 これだけでも十分便利そうだが、このように List 決め打ちの関数が出てきたら、 何か良い型クラスで置換できないかを疑ってみるべきだ。

McBride さんと Paterson さんは、まず sequence 関数の MonadApplicative に置換して、dist として一般化した:

def dist[G[_]: Applicative, A](gas: List[G[A]]): G[List[A]]

次に、distmap と一緒に呼ばれることが多いことに気付いたので、 アプリカティブ関数をパラメータとして追加して、これを traverse と呼んだ:

def traverse[G[_]: Applicative, A, B](as: List[A])(f: A => G[B]): G[List[B]]

最後に、このシグネチャを型クラスとして一般化したものが Traversible 型クラスと呼ばれるものとなった:

@typeclass trait Traverse[F[_]] extends Functor[F] with Foldable[F] { self =>

  /**
   * given a function which returns a G effect, thread this effect
   * through the running of this function on all the values in F,
   * returning an F[A] in a G context
   */
  def traverse[G[_]: Applicative, A, B](fa: F[A])(f: A => G[B]): G[F[B]]

  /**
   * thread all the G effects through the F structure to invert the
   * structure from F[G[_]] to G[F[_]]
   */
  def sequence[G[_]: Applicative, A](fga: F[G[A]]): G[F[A]] =
    traverse(fga)(ga => ga)
  ....
}

そのため、歴史の必然として Traverse はデータ型ジェネリックな sequence 関数を実装する。 言ってみれば traverseidentity を渡しただけなんだけど、 F[G[A]]G[F[A]] にひっくり返しただけなので、コンセプトとして覚えやすい。 標準ライブラリの Future に入ってるこの関数として見たことがあるかもしれない。

scala> import scala.concurrent.{ Future, ExecutionContext, Await }
import scala.concurrent.{Future, ExecutionContext, Await}

scala> import scala.concurrent.duration._
import scala.concurrent.duration._

scala> val x = {
         implicit val ec = scala.concurrent.ExecutionContext.global
         List(Future { 1 }, Future { 2 }).sequence
       }
x: scala.concurrent.Future[List[Int]] = List()

scala> Await.result(x, 1 second)
res4: List[Int] = List(1, 2)

EitherList をまとめて Either にするとか便利かもしれない。

scala> List(Right(1): Either[String, Int]).sequenceU
res5: scala.util.Either[String,List[Int]] = Right(List(1))

scala> List(Right(1): Either[String, Int], Left("boom"): Either[String, Int]).sequenceU
res6: scala.util.Either[String,List[Int]] = Left(boom)

sequenceUnapply 版である sequenceU を使ったことに注意。 続いては、これを見ることにする。