Invariant Shadows - Part 2: Monoidals

In the last post, we built type classes for a subset of invariant functors – namely, type classes that drew inspiration from the covariant FlatMap and Monad. In this article, we’ll explore invariant shadows of the type classes supporting applicative functors.

Disclaimer: I am not a category theorist, and in both the previous article and this article, I use fairly loose reasoning to explore these type classes. Corrections are welcome.

First, let’s review the definition of an applicative functor, using a type class hierachy similar to the one used in Cats. (These examples are simplified versions of the definitions in the Cats codebase.)

trait Apply[F[_]] extends Functor[F] {
  def ap[A, B](fa: F[A])(ff: F[A => B]): F[B]
}

trait Applicative[F[_]] extends Apply[F] {
  def pure[A](a: A): F[A]
  def map[A, B](fa: F[A])(f: A => B): F[B] = ap(fa)(pure(f))
}

Along with laws:

def applyComposition[F[_], A, B, C](fa: F[A], fab: F[A => B], fbc: F[B => C])(implicit F: Apply[F]): Boolean = {
  val compose: (B => C) => (A => B) => (A => C) = _.compose
  F.ap(F.ap(fa)(fab))(fbc) == F.ap(fa)(F.ap(fab)(F.map(fbc)(compose)))
}

def applicativeIdentity[F[_], A](fa: F[A])(implicit F: Applicative[F]): Boolean =
  F.ap(fa)(F.pure((a: A) => a)) == fa

def applicativeHomomorphism[F[_], A, B](a: A, f: A => B)(implicit F: Applicative[F]): Boolean =
  F.ap(F.pure(a))(F.pure(f)) == F.pure(f(a))

def applicativeInterchange[F[_], A, B](a: A, ff: F[A => B])(implicit F: Applicative[F]): Boolean =
  F.ap(F.pure(a))(ff) == F.ap(ff)(F.pure((f: A => B) => f(a)))

def applicativeMap[F[_], A, B](fa: F[A], f: A => B)(implicit F: Applicative[F]): Boolean =
  F.map(fa)(f) == F.ap(fa)(F.pure(f))

Applicative[Codec]

Can we define an Applicative[Codec] instance? We’ve previously seen how Codec has an invariant functor instance but not a covariant functor instance. As such, we can rule out an Applicative[Codec], for if we could define such an instance, it would give rise to a Functor[Codec]. Regardless, let’s try to implement such an instance, as it is illustrative.

In the last article, it was implied that we can implement pure for Codec. Here’s an implementation:

def pure[A](a: A): Codec[A] = new Codec[A] {
  def sizeBound = SizeBound.exact(0)
  def encode(a: A) = Attempt.successful(BitVector.empty)
  def decode(b: BitVector) = Attempt.successful(DecodeResult(a, b))
}

The encode operation always returns an empty vector, while the decode operation always returns the full input as the remainder and returns the pure value as the decoded value.

How about ap?

def ap[A, B](ca: Codec[A])(cf: Codec[A => B]): Codec[B] = new Codec[B] {
  def sizeBound = SizeBound.unknown
  def decode(b: BitVector) = (for {
    decA <- DecodingContext(ca)
    defF <- DecodingContext(cb)
  } yield decF(decA)).decode(b)
  def encode(b: B) = {
    ???
  }
}

The decode case is easy enough to define using the DecodingContext type from scodec, which is equivalent to a StateT[Attempt, BitVector, ?] monad transformer stack, threading the remainder of each decode as the state value. We encounter an impasse in encode though. We could try to add a B => A function, though it is not obvious as to how that would help. Instead, we can use an alternative form of applicative functors known as monoidal functors.

Monoidal Functors

(Lax) monoidal functors are an alternative form of applicative functors – similar to how monads can be represented with either pure and flatMap or unit, flatten (aka join), and map.

trait Monoidal[F[_]] extends Functor[F] {
  def unit: F[Unit]
  def zip[A, B](fa: F[A], fb: F[B]): F[(A, B)]
}

Instead of defining pure and ap, monoidal functors are defined in terms of unit, zip, and map. Note that in the standard/typical definition, map is derived from pure and ap but in the monoidal definition, map is left abstract.

The laws for monoidal functors are the following:

trait Iso[A, B] { def apply(a: A): B }

implicit class IsoOps[A](val a: A) {
  def ~=[B](b: B)(implicit iso: Iso[A, B]): Boolean = iso(a) == b
}

def monoidalLeftIdentity[F[_], A](fa: F[A])(implicit F: Monoidal[F], iso: Iso[F[(Unit, A)], F[A]]): Boolean =
  F.zip(F.unit, fa) ~= fa

def monoidalRightIdentity[F[_], A](fa: F[A])(implicit F: Monoidal[F], iso: Iso[F[(A, Unit)], F[A]]): Boolean =
  F.zip(fa, F.unit) ~= fa

def monoidalAssociativity[F[_], A, B, C](fa: F[A], fb: F[B], fc: F[C])(implicit F: Monoidal[F], iso: Iso[F[(A, (B, C))], F[((A, B), C)]]): Boolean =
  F.zip(fa, F.zip(fb, fc)) ~= F.zip(F.zip(fa, fb), fc)

The identity laws state that zipping a value with the unit value yields the original value, ignoring the tuple structure. The associativity law requires zip to be associative, again ignoring the tuple structure. Here, like in the Typeclassopedia definition, we defer the equality checking to an isomorphism that ignores the unwanted structure.

We could further generalize this type class by removing the requirement for the unit and map operations, leaving simply zip along with the associativity law – this is exactly what Scalaz has done with the scalaz.Zip type class.

Converting applicative forms

We can convert any applicative functor to a monoidal functor and vice-versa:

implicit def applicativeToMonoidal[F[_]](implicit F: Applicative[F]): Monoidal[F] = new Monoidal[F] {
  def unit: F[Unit] = F.pure(())
  def zip[A, B](fa: F[A], fb: F[B]): F[(A, B)] = F.ap(fb)(F.map(fa)(a => (b: B) => (a, b)))
  def map[A, B](fa: F[A])(f: A => B): F[B] = F.map(fa)(f)
}

implicit def monoidalToApplicative[F[_]](implicit F: Monoidal[F]): Applicative[F] = new Applicative[F] {
  def pure[A](a: A): F[A] = F.map(F.unit)(_ => a)
  def ap[A, B](fa: F[A])(ff: F[A => B]): F[B] = F.map(F.zip(fa, ff)) { case (a, f) => f(a) }
}

Monoidal[Codec]

Let’s try to implement a Monoidal instance for Codec.

The definition of unit looks very similar to the definition of pure:

def unit: Codec[Unit] = new Codec[Unit] {
  def sizeBound = SizeBound.exact(0)
  def encode(a: A) = Attempt.successful(BitVector.empty)
  def decode(b: BitVector) = Attempt.successful(DecodeResult((), b))
}

Now let’s try to implement zip – note that we should not be able to, as we know Codec doesn’t have a covariant functor.

def zip[A, B](ca: Codec[A], cb: Codec[B]): Codec[(A, B)] = new Codec[(A, B)] {
  def sizeBound = ca.sizeBound + cb.sizeBound
  def decode(b: BitVector) = (for {
    a <- DecodingContext(ca)
    b <- DecodingContext(cb)
  } yield (a, b)).decode(b)
  def encode(ab: (A, B)) = for {
    encA <- ca.encode(ab._1)
    encB <- cb.encode(ab._2)
  } yield encA ++ encB
}

Wait, so what are we missing? We have an implementation of unit and zip and yet we know we can’t have a lawful Monoidal[Codec] instance due to the fact that there’s no covariant functor for Codec. Monoidal functors have three abstract operations though, not two (like Applicative) – unit, zip, and map. So in order to have a monoidal functor for Codec, we need to define map, which we know we can’t do!

However, we do have xmap. What happens if we pair xmap with unit and zip?

Invariant monoidal functors

Let’s define a new invariant shadow of Monoidal that extends InvariantFunctor instead of Functor:

trait InvariantMonoidal[F[_]] extends InvariantFunctor[F] {
  def unit: F[Unit]
  def zip[A, B](fa: F[A], fb: F[B]): F[(A, B)]
}

We can also port the laws from lax monoidal functors, which are identical except for requiring an InvariantMonoidal instance instead of a Monoidal instance:

def xmonoidalLeftIdentity[F[_], A](fa: F[A])(implicit F: InvariantMonoidal[F], iso: Iso[F[(Unit, A)], F[A]]): Boolean =
  F.zip(F.unit, fa) ~= fa

def xmonoidalRightIdentity[F[_], A](fa: F[A])(implicit F: InvariantMonoidal[F], iso: Iso[F[(A, Unit)], F[A]]): Boolean =
  F.zip(fa, F.unit) ~= fa

def xmonoidalAssociativity[F[_], A, B, C](fa: F[A], fb: F[B], fc: F[C])(implicit F: InvariantMonoidal[F], iso: Iso[F[(A, (B, C))], F[((A, B), C)]]): Boolean =
  F.zip(fa, F.zip(fb, fc)) ~= F.zip(F.zip(fa, fb), fc)

Deriving an InvariantMonoidal from an InvariantMonad

In the same way that a monad yields two monoidal functors (or two applicative functors) – one that evaluates F[A] first and F[B] second, and another which evaluates in the reverse order – an invariant monad gives rise to two invariant monoidal functors. For example, the following implementation evaluates the F[A] first and the F[B] second:

implicit def xmonadToXmonoidal[F[_]](implicit F: InvariantMonad[F]): InvariantMonoidal[F] = new InvariantMonoidal[F] {
  def unit: F[Unit] = F.pure(())
  def zip[A, B](fa: F[A], fb: F[B]): F[(A, B)] =
    F.xflatMap(fa)(a => F.xmap(fb)(b => (a, b))(ab => ab._2))(ab => ab._1)
  def xmap[A, B](fa: F[A])(f: A => B)(g: B => A): F[B] = F.xmap(fa)(f)(g)
}

Sharing unit/zip

Because the invariant monoidal differs from the covariant monoidal only in the defintion of xmap/map, we could extract a type class that captures the signature of unit and zip and the laws that govern their interaction.

trait MonoidalBase[F[_]] {
  def unit: F[Unit]
  def zip[A, B](fa: F[A], fb: F[B]): F[(A, B)]
}
trait Monoidal[F[_]] extends MonoidalBase[F] with Functor[F]
trait InvariantMonoidal[F[_]] extends MonoidalBase[F] with InvariantFunctor[F]

Applicability to Codec

In the last article, we saw that Codec supported both flatZip and consume, and how those methods exist due to the invariant monad structure of Codec. In fact, those methods both existed before the invariant monad structure was extracted. Is the same true for unit and zip? That is, do those methods exist under some other name, their existence justified by their usefulness in binary codec creation, rather than satisfying a type class definition?

It turns out that both of these operations do exist already. The unit operation is provided by scodec.codecs.ignore(0L), which returns a Codec[Unit] that encodes an empty bit vector. The zip operation is provided by the pairedWith method on codec – which has the operator alias ~.

We did not provide an invariant shadow of applicative functors, though that is worth exploring, perhaps in a future article.