Shape and contents 

EIP:

In addition to being parametrically polymorphic in the collection elements, the generic traverse operation is parametrised along two further dimensions: the datatype being traversed, and the applicative functor in which the traversal is interpreted. Specialising the latter to lists as a monoid yields a generic contents operation:

Here’s how we can implement this with Cats:

scala> import cats._, cats.data._, cats.implicits._
import cats._
import cats.data._
import cats.implicits._

scala> 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.traverseU(fa)(contentsBody)
         }
contents: [F[_], A](fa: F[A])(implicit FF: cats.Traverse[F])cats.data.Const[List[A],F[Unit]]

Now we can take any datatype that supports Traverse and turn it into a List.

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

I am actually not sure if the result suppose to come out in the reverse order here.

The other half of the decomposition is obtained simply by a map, which is to say, a traversal interpreted in the identity idiom.

When Gibbons say identity idiom, he means the identity applicative functor, Id[_].

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

Here’s the shape for Vector(1, 2, 3):

scala> shape(Vector(1, 2, 3))
res1: cats.Id[scala.collection.immutable.Vector[Unit]] = Vector((), (), ())

EIP:

This pair of traversals nicely illustrates the two aspects of iterations that we are focussing on, namely mapping and accumulation.

Next EIP demonstrates applicative composition by first combining shape and contents together like this:

scala> def decompose[F[_], A](fa: F[A])(implicit FF: Traverse[F]) =
         Prod[Const[List[A], ?], Id, F[Unit]](contents(fa), shape(fa))
decompose: [F[_], A](fa: F[A])(implicit FF: cats.Traverse[F])cats.data.Prod[[β]cats.data.Const[List[A],β],cats.Id,F[Unit]]

scala> val d = decompose(Vector(1, 2, 3))
d: cats.data.Prod[[β]cats.data.Const[List[Int],β],cats.Id,scala.collection.immutable.Vector[Unit]] = Prod(Const(List(1, 2, 3)),Vector((), (), ()))

scala> d.first
res2: cats.data.Const[List[Int],scala.collection.immutable.Vector[Unit]] = Const(List(1, 2, 3))

scala> d.second
res3: cats.Id[scala.collection.immutable.Vector[Unit]] = Vector((), (), ())

The problem here is that we are running traverse twice.

Is it possible to fuse the two traversals into one? The product of applicative functors allows exactly this.

Let’s try rewriting this using AppFunc.

scala> import cats.data.Func.appFunc
import cats.data.Func.appFunc

scala> def contentsBody[A]: AppFunc[Const[List[A], ?], A, Unit] =
         appFunc[Const[List[A], ?], A, Unit] { (a: A) => Const(List(a)) }
contentsBody: [A]=> cats.data.AppFunc[[β]cats.data.Const[List[A],β],A,Unit]

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

scala> def decompose[F[_], A](fa: F[A])(implicit FF: Traverse[F]) =
         (contentsBody[A] product shapeBody[A]).traverse(fa)
decompose: [F[_], A](fa: F[A])(implicit FF: cats.Traverse[F])cats.data.Prod[[β]cats.data.Const[List[A],β],cats.Id,F[Unit]]

scala> val d = decompose(Vector(1, 2, 3))
d: cats.data.Prod[[β]cats.data.Const[List[Int],β],cats.Id,scala.collection.immutable.Vector[Unit]] = Prod(Const(List(1, 2, 3)),Vector((), (), ()))

scala> d.first
res4: cats.data.Const[List[Int],scala.collection.immutable.Vector[Unit]] = Const(List(1, 2, 3))

scala> d.second
res5: cats.Id[scala.collection.immutable.Vector[Unit]] = Vector((), (), ())

The return type of the decompose is a bit messy, but it’s infered by AppFunc: Prod[[X_kp1]Const[List[A], X_kp1], Id, F[Unit]].