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:

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)
  }

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

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[_].

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)
  }

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

shape(Vector(1, 2, 3))
// res1: Id[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:

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((), (), ())

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.

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((), (), ())

The return type of the decompose is a bit messy, but it’s infered by AppFunc: Tuple2K[Const[List[Int], β1], Id[A], Vector[Unit]].