形とコンテンツ 

EIP:

要素の収集に関してパラメトリックに多相であることの他に、 このジェネリックな traverse 演算はもう 2つの次元によってパラメータ化されている: traverse されるデータ型と、traversal が解釈されるアプリカティブ・ファンクターだ。 後者をモノイドとしてのリストに特化すると、ジェネリックな contents 演算が得られる。

Cats を用いて実装するとこうなる:

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

def contents[F[_], A](fa: F[A])(implicit FF: Traverse[F]): Const[List[A], F[Unit]] =
  {
    val contentsBody: A => Const[List[A], Unit] = { (a: A) => Const(List(a)) }
    FF.traverse(fa)(contentsBody)
  }

これで Traverse をサポートする任意のデータ型から List を得られるようになった。

contents(Vector(1, 2, 3)).getConst
// res0: List[Int] = List(1, 2, 3)

これが逆順になっているのは果たして正しいのか、ちょっと定かではない。

分解の片方は、単純な写像 (map)、つまり恒等アプリカティブ・ファンクターによって解釈される traversal から得ることができる。

恒等アプリカティブ・ファンクターとは Id[_] のことだというのは既にみた通り。

def shape[F[_], A](fa: F[A])(implicit FF: Traverse[F]): Id[F[Unit]] =
  {
    val shapeBody: A => Id[Unit] = { (a: A) => () }
    FF.traverse(fa)(shapeBody)
  }

Vector(1, 2, 3) の形はこうなる:

shape(Vector(1, 2, 3))
// res1: Id[Vector[Unit]] = Vector((), (), ())

EIP:

この traversal のペアは、ここで取り上げている反復の 2つの側面、 すなわち写像 (mapping) と累積 (accumulation) を体現するものとなっている。

次に、EIP はアプリカティブ合成を説明するために shape と contents を以下のように組み合わせている:

def decompose[F[_], A](fa: F[A])(implicit FF: Traverse[F]) =
  Tuple2K[Const[List[A], *], Id, F[Unit]](contents(fa), shape(fa))

val d = decompose(Vector(1, 2, 3))
// d: Tuple2K[Const[List[Int], β0], Id, Vector[Unit]] = Tuple2K(
//   first = Const(getConst = List(1, 2, 3)),
//   second = Vector((), (), ())
// )

d.first
// res2: Const[List[Int], Vector[Unit]] = Const(getConst = List(1, 2, 3))

d.second
// res3: Id[Vector[Unit]] = Vector((), (), ())

問題は traverse が 2回走っていることだ。

これら2つの走査 (traversal) を 1つに融合 (fuse) させることはできないだろうか? アプリカティブ・ファンクターの積は正にそのためにある。

これを AppFunc で書いてみよう。

import cats.data.Func.appFunc

def contentsBody[A]: AppFunc[Const[List[A], *], A, Unit] =
  appFunc[Const[List[A], *], A, Unit] { (a: A) => Const(List(a)) }

def shapeBody[A]: AppFunc[Id, A, Unit] =
  appFunc { (a: A) => ((): Id[Unit]) }

def decompose[F[_], A](fa: F[A])(implicit FF: Traverse[F]) =
  (contentsBody[A] product shapeBody[A]).traverse(fa)

val d = decompose(Vector(1, 2, 3))
// d: Tuple2K[Const[List[Int], β1], Id[A], Vector[Unit]] = Tuple2K(
//   first = Const(getConst = List(1, 2, 3)),
//   second = Vector((), (), ())
// )

d.first
// res5: Const[List[Int], Vector[Unit]] = Const(getConst = List(1, 2, 3))

d.second
// res6: Id[Vector[Unit]] = Vector((), (), ())

decompose　の戻り値の型が少しごちゃごちゃしてきたが、AppFunc によって推論されている: Tuple2K[Const[List[Int], β1], Id[A], Vector[Unit]].