### 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.traverse(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.traverse(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]) =
Tuple2K[Const[List[A], ?], Id, F[Unit]](contents(fa), shape(fa))
decompose: [F[_], A](fa: F[A])(implicit FF: cats.Traverse[F])cats.data.Tuple2K[[β\$0\$]cats.data.Const[List[A],β\$0\$],cats.Id,F[Unit]]
scala> val d = decompose(Vector(1, 2, 3))
d: cats.data.Tuple2K[[β\$0\$]cats.data.Const[List[Int],β\$0\$],cats.Id,scala.collection.immutable.Vector[Unit]] = Tuple2K(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[[β\$0\$]cats.data.Const[List[A],β\$0\$],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.Tuple2K[[β\$0\$]cats.data.Const[List[A],β\$0\$],cats.Id,F[Unit]]
scala> val d = decompose(Vector(1, 2, 3))
d: cats.data.Tuple2K[[β\$0\$]cats.data.Const[List[Int],β\$0\$],cats.Id,scala.collection.immutable.Vector[Unit]] = Tuple2K(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`: `Tuple2K[[X_kp1]Const[List[A], X_kp1], Id, F[Unit]]`.