Comonads and Authentication as Context

Table of contents

• Comonads and Authentication as Context
  • What is a comonad?
    • Loose Discursus: Duality
    • Dualizing Monads
      • Dualizing `pure`
      • Dualizing `flatMap`
      • Comonads
  • Authentication as Context
    • Authentication Comonad
    • Aside: Comonads and Compositionality
    • Authenticated Application Logic as Cokleisli
    • Authenticated Requests and http4s DSL
      • Generically Contextual Routes
  • Conclusion

Sometimes I don't have a fully fleshed out design, or even really an idea, but just an intention to explore a space. I often find that writing is an okay way to start to think out those ideas, even if they don't obviously go to something shippable.

This is one of those. You shouldn't really expect everything here to be fully worked out or confirmed to be working, this is more a gesture in a direction and an attempt to connect some ideas together.

What is a comonad?

Eventually, I want to try and think about one way you might model a phenemonen using an abstraction called a comonad, but to do that we have to get to a place where we can talk about that concept.

So, to start with, let's try to talk about duality.

Loose Discursus: Duality

I'll start here, speaking intentionally at a largely non-rigourous level¹. Many functional programmers are familiar with the concept of a Monad. If you aren't, I won't be getting into it here, but there are many introductions here and there, of variable quality². So come back later.

Most such programmers are aware the concept has a lineage descending from category theory. A smaller subset of same are aware of and, and likely smaller yet have a grasp on, the concept of duality, a central concept in category theory

In category theory, notions are determined rigorously by the structural relations they describe between items, these are drawn as arrows in diagrams. For example, a diagram like this could describe some structure that would determine a general notion:

A -> B
|    |
v    v
C -> D

Duality is what happens when we just reverse those arrows. So, taking that last diagram you'd get this:

A <- B
^    ^
|    |
C <- D

Those are dual to each other, the relationships are reversed, broadly speaking.

If you are following, you can see where I am going. Monads are category theoretic, so they should be desribed by a diagram. What do you get if you dualize that diagram³?

Dualizing Monads

Let's recall the traditional encoding of the monad in Scala.

trait Monad[F[_]] {
  def pure[A](a: A): F[A]
  def flatMap[A, B](fa: F[A], f: A => F[B]): F[B]
}

This should be familiar to you, broadly speaking. So, how would this dualize?

In general, you should think of the type signature of a method as a kind of arrow from the input to the output type, considering them as objects in the category of types modeled by our language.

As a convention, in category theoretic settings, to reduce the density of terminology, one usually just prepends the prefix co- to a notion in order to denote its dual. So Monad becomes Comonad.

I'll rely on this occasionally, so let that inform your thinking if it helps.

Let's take this method by method, try to dualize each method one by one.

Dualizing `pure`

So you might, non-rigorously, imagine pure as:

A -> F[A]

In other words, pure takes any value in the world, and embeds itself into the monad -- it puts it into context. This might be making it the head of a List, whatever, it adds more information, structurally.

How would we dualize pure? Well, clearly the contextual value should be the argument, and it should be, as it were, denuded in the result. Something like:

F[A] -> A

In other words, in syntax, we should end up with:

def copure[A](a: F[A]): A

Seems reasonable right? If a Monad puts anything into itself freely, a Comonad should release any value bound into itself back out into the world without issue.

This method is normally called extract:

def extract[A](a: F[A]): A

It describes the ability for any Comonad context to be stripped away, regardless of the inner type.

Note that this excludes things like List! Afterall, consider, what should the outcome of the following expression be:

extract(Nil)

I think it's clear there can be no meaningful answer that has the appropriate type for any type A that you provide⁴.

Afterall, if there were, this would be true (because the input is the same value on both sides!):

extract[Int](Nil) == extract[String](Nil)

But this is impossible, as an Int and a String can never belong to the same domain⁵.

Dualizing `flatMap`

Alright how would we draw flatMap, very non-rigorously⁶? Like this probably:

F[A] -> (A -> F[B]) -> F[B]

Remebering to reverse the inner arrow, then a dual would look like this:

F[B] -> (F[B] -> A) -> F[A]

Let's try to realize that syntactically:

def coflatMap[A, B](fa: F[A], f: F[A] => B): F[B]

So, flatMap normally means: given an element of type A in context F and a way of turning an element of type A into contextualized element of another type F[B], you get a contextualized elemnt of the F[B]. Like, you can have a List[A], and a function A => List[B] and get List[B], the result of flattening all result lists, right?

Well, then the signature we have here says something kind of different. It says someting like given a contextualized value F[A] and a way of interpreting contextualized values into values of type B we can produce a contextualized value of type F[B]. As discussed above, we can't do this with List, but it might be worth thinking briefly about what it might look like if we could implement extract for List⁷.

I'm teasing you about this List stuff, but we're going to do it in the next section, because it turns out we've now gotten all the ingredients for a Comonad.

Comonads

We now have the ingredients we need, so let's dualize our Monad totally, again ignoring rigor and laws for this blogpost.

Lo, comonad:

trait Comonad[F[_]] {
  def coflatMap[A, B](fa: F[A], f: F[A] => B): F[B]
  def extract[A](fa: F[A]): A

  // Gotta have this to have it be a `Functor`, which is desirable.
  def map[A, B](fa: F[A])(f: A => B): F[B]
}

Kind of fun, right? Who knows what it's good for. Let's find something it's good for, I guess?

Well, for one, NonEmptyList is a canonical example. As a reminder, here's how you might define a NonEmptyList:

sealed abstrct case class NonEmptyList[A](
  head: A,
  tail: List[A]
)

Let's write the implementation for Comonad:

// Shorthand for convenience in formatting
type Nel[A] = NonEmptyList[A]
implicit val comonadForList: Comonad[Nel] =
  new Comonad[Nel] {
    // a NonEmptyList always has a head
    def extract[A](a: Nel[A]): A =
      a.head

    // A NonEmptyList always has a tail, or itself to compute with
    def coflatMap[A, B](fa: Nel[A])(
      f: Nel[A] => B
    ): Nel[B] =
      fa match {
        // If it doesn't have a tail, consume the given Nel, we're done
        case x @ Nel(_, List()) => Nel(f(x), Nil)
        // If it has a tail, you recurse and consume each sublist to
        // produce a new element of our new list, while consuming the
        // whole to produce the head of the non-empty list
        case x @ Nel(_, ls) => {
          val r = Nel(ls.head, ls.tail).coflatMap(f)
          Nel(f(x), r.head :: r.tail)
        }

      }

    // This isn't very novel, so bootstrapping from `List`
    def map[A, B](fa: Nel[A])(f: A => B): Nel[B] =
      Nel(f(a), ls.map(f))
  }

This implementation is I think pretty straight forward while still being interesting. The coflatMap lets us summarize each substructure, here each non-empty sublist of the original non-empty list.

NonEmptyList(5, List(4, 3, 2, 1))
  .coflatMap(_.fold)

// Results in the first 5 triangle numbers:
NonEmptyList(
  15,
  List(
    10,
    6
    3
    1
  )
)

An important difference between Comonad and Monad is it's not generically obvious how to put a value into a Comonadic context.

With Monad we have this interface available:

trait Monad[F[_]] {
  def flatMap[A, B](fa: F[A], f: A => F[B]): F[B]
  def pure[A](a: A): F[A]
}

So given any A we can just toss pure at it and get an F[A], for any type A! But if you look back to Comonad, we have no such similar power. We do have the dual power to always lose our context, which a Monad doesn't provide, and that's interesting.

This is an important difference! Monads are very welcoming but hold their values tightly, while Comonads are very guarded and hold their values very loosely. Easy come, not so easy go versus not so easy come very easy go.

Authentication as Context

If we're looking for other domains that might behave comonadically, then we should keep those intuitions close to our hearts.

What's a kind of context that is difficult to obtain, but unimportant to consume?

Well, I think you can argue the status of being authenticated is such a context.

You definitely don't want it to be monadic! Afterall, the state of being authenticated should be earned with evidence, otherwise anything at all could be authenticated.

On the other hand, once you have authenticated that evidence or status of being authenticated need not be relevant for every function that once to interact with the authenticated data - that would be really annoying and sort of pointless (not all operations are identity relevant, for example).

Authentication Comonad

So, we could imagine implementing some kind of data structure that reifies the status of a request being authenticated, and then a way for that authenticated context to track along with data downstream of processing that request.

If we did that, maybe we could then implement Comonad for that data structure!

Let's give it a go:

// Take for granted that we have some type of evidence
// Maybe it's a validated JWT or something, whatever
type Evidence
sealed abstract case class Authenticated[A](
  evidence: Evidence,
  value: A
)

Okay, so far so good, seems legitimate. We've expressed the core idea: reify the idea of a value being from an authenticated context, attach our authenticated evidence, and leave open the value held. Since the case class is sealed abstract, no one can construct such a value outside of our file.

If we assume that the appropriate validators and so forth are also written in this file and only they construct Authenticated values, we've provided a reasonable contract⁸.

Let's try to implement Comonad. We need two methods: extract and coflatMap.

Starting with the simplest, extract, should be straightforward:

def extract[A](authed: Authenticated[A]): A =
  authed.value

We just forget that the value is authenticated by grabbing the inner value off of the Authenticated context value.

What about coflatMap?

def coflatMap[A, B](
  authed: Authenticated[A],
  f: Authenticated[A] => B
): Authenticated[B] =
  new Authenticated(authed.evidence, f(authed)) {}

It's really that simple! Just wrap the result of consuming the authenticated value in the context, carrying forward the evidence that it is authenticated.

Now, really, we'd have to test this passes all the laws for Comonad but like I said we're bracketing that for this blog post. You can easily write a test using cats-laws that shows it does indeed pass the laws (shouldn't be surprising, there's in a way not a lot of content here⁹).

How would we use this? Well, in a framework like finch or http4s, we'd want a combinator that wraps an endpoint, validating the request and then coflatMaping the function the endpoint executes against the authenticated structure.

Aside: Comonads and Compositionality

As an aside, the reason why having something be a Comonad is interesting is because like getting a Monad, you get a novel form of composability out of it.

One of the important affordances granted by a Monad is our ability to use for comprehensions.

For example, supposing we have functions like:

// For some types A, B, C, and some imagined implementation
def first(value: A): Option[B] = ???
def second(value: B): Option[C] = ???
def second(value: C): Option[D] = ???

We could write something like:

val comp: Option[D] =
  for {
    intermediate <- first(value)
    next <- second(intermediate)
    result <- third(next)
  } yield result

And this is desugared into something like:

val comp: Option[D] =
  first(value)
    .flatMap(second)
    .flatMap(third)
    .map(result => result)

Comonads, in principle, allow a similar but dual affordance¹⁰!

Given some functions for NonEmptyList:

// For some types A, B, C, and some imagined implementation
def first(value: A): NonEmptyList[B] = ???
def second(value: B): NonEmptyList[C] = ???
def second(value: C): NonEmptyList[D] = ???

We could imagine desugaring this¹¹:

val comp: NonEmptyList[A] => D =
  cofor (value) {
    intermediate <- first(value)
    next <- second(intermediate)
    result <- third(next)
  } yield result

Into something like this:

val comp: NonEmptyList[A] => D =
  _.coflatMap(first)
    .coflatMap(second)
    .coflatMap(third)
    .map(result => result)

In other words, we get a nice notion of composition for our computations that consume Authenticated context now that we have it proved it out as a Comonad. We can essentially thread that context through all of our subsequent computations cleanly and transparently without having to manage it manually.

Authenticated Application Logic as Cokleisli

Okay, now, back outside the Ivory Tower let's get back to thinking about our Authenticated context and how we might work with it.

Let's try to sketch this briefly in http4s, which conveniently gives me an excuse to relearn some of how it works, again.

First, we can imagine how we'd implement some endpoint's business logic. Maybe something like deleteProfile.

Definitely, that should be beind some sort of authentication / authorization scheme. For now, let's assume that users are the only ones allowed to delete their own profile, directly, so all we need is that they are appropriately authenticated.

Perhaps something like this:

case class DeleteUserRequest(
  userId: String
)

// Returns `IO` because has to do some side effect against a database
def deleteUser(
  deletion: Authenticated[DeleteUserRequest]
): OptionT[IO, Unit] =
  OptionT.liftF[IO, Unit](db.deleteUser(deletion.value.userId))

This is a sort of interesting type signature - it's the type of thing one would pass to coflatMap, namely:

Authenticated[A] => B

This is the dual to a type called Kleisli, called Cokleisli¹². You could write it like this:

// `Cokleisli` for a `Comonad` named `F`
type Cokleisli[F[_], A, B] = F[A] => B

// compare with the more traditional `Kleisli` for `Monad`:
type Kleisli[F[_], A, B] = A => F[B]

So, our deleteUser looks sort of like a Cokleisli for Authenticated. We've also got an IO on the return end, though.

Recall that in http4s, endpoints are typed as, if we're using cats-effect:

Kleisli[OptionT[IO, *], Request[IO], Response[IO]]
// Expanding the `Kleisli` we get:
Request[IO] => OptionT[IO, Response[IO]]
// Expanding the `OptionT` we get:
Request[IO] => IO[Option[Response[IO]]]

So, we've got some interesting concepts floating around each other here — http4s wants a Kleisli to IO plus some other stuff, and we have a Cokleisli that returns an IO of something.

Authenticated Requests and http4s DSL

If we were to use our deleteUser function in a sample http4s DSL:

val service = HttpRoutes.of[IO] {
  case req @ POST -> Root / "deleteUser" =>
    for {
      request <- req.as[DeleteUserRequest]
      _ <- deleteUser(request)
    } yield ()
}

This would fail to compile! We haven't provided the appropriate Authenticated data, so deleteUser rightfully complains.

Let's assume the data we need is provided by headers:

def authenticate[A](
  jwt: String,
  value: A
): IO[Authenticated[A]] =
  JWTValidator.validate(jwt)
    .map(evidence => Authenticated(evidence, value))

val service = HttpRoutes.of[IO] {
  case req @ POST -> Root / "deleteUser" =>
    for {
      jwt <- OptionT.fromOption[IO](
        req.headers.get[headers.Authorization]
      )
      request <- OptionT.fromOption[IO](
        req.as[DeleteUserRequest].toOption
      )
      authed <- OptionT.liftF(
        authenticate(jwt, request)
      )
      _ <- deleteUser(authed)
    } yield ()
}

This ought to work! We've given http4s a function of type Request[IO] => OptionT[IO, Response[IO]]!

But, sadly, our Authenticated types no longer appear in the type signature. This is sort of a shame, it would be nice if we could see directly in the signature of our API which endpoints have authentication, and which do not¹³.

Additionally, if we had multiple such endpoints, we'd be doing the auth check in each one, which would be easy to screw up.

Can we restore tracking of our Authenticated types and centralize our auth check?

The most natural strategy is to reflect our distinction back into the syntax, so we can define a helper to group the routes that use authentication and have a different signature:

object AuthenticatedRoutes {
  def of[F[_]: Monad](
    validator: Request[F] => Authenticated[Request[F]]
  )(
    route: PartialFunction[
      Request[F],
      Cokleisli[Authenticated, Request[F], OptionT[F, Response[F]]]]
  ): Kleisli[OptionT[F, *], Request[F], Response[F]] =
    Kleisli(
      req => route(req).run(validator(req))
    )
}

Basically, we pass the request to our pattern matching routes, and if it succeeds we validate the request, and then run it against the matched handler. Then, we package this logic up into a Kleisli to return back into our http4s machinery.

But in order to use this meaingfully we're going to need a way to interchange Authenticated and IO. To see why, take a look at this code:

def service =
    AuthenticatedRoutes.of(req =>
      IO.fromOption(req.headers.get[headers.Authorization])
        .flatMap(authenticate(_, req))
    ) {
      case POST -> root / "deleteUser" =>
        Cokleisli(authedReq =>
          for {
            request <-
              authedReq.map(_.as[DeleteUserRequest])
                .map(IO.fromEither)
                .map(OptionT.liftF)
            _ <- deleteUser(request)
          } yield ()
        )
    }
}

This looks plausible enough, but it fails to compile! Namely, the RHS of the first arrow is Authenticated[OptionT[IO, DeleteUserRequest]], but that's not a Monad!

If we could interchange Authenticated and IO (or really OptionT[IO, *]) then we'd have everything we need.

The seasoned functional programmer is immediately thinking "You need Traverse!".

Indeed, we can write a Traverse for Authenticated:

// Skipping the `map` implementation since it's given above
implicit val traverse: Traverse[Authenticated] =
  new Traverse[Authenticated {
    def traverse[G[_]: Applicative, A, B](fa: Authenticated[A])(f: A => G[B]): G[Authenticated[B]] =
      f(fa.value).map(v => Authenticated(fa.evidence, v))

    def foldLeft[A, B](fa: Authenticated[A], b: B)(f: (B, A) => B): B =
      f(b, fa.value)

    def foldRight[A, B](fa: Authenticated[A], lb: Eval[B])(f: (A, Eval[B]) => Eval[B]): Eval[B] =
      f(fa.value, lb)
  }

Then, we just sprinkle some traverse and we're off to the races:

def service =
    AuthenticatedRoutes.of(req =>
      IO.fromOption(req.headers.get[headers.Authorization])
        .flatMap(authenticate(_, req))
    ) {
      case POST -> root / "deleteUser" =>
        Cokleisli(authedReq =>
          for {
            request <-
              authedReq.map(_.as[DeleteUserRequest])
                .map(IO.fromEither)
                .traverse(OptionT.liftF)
            _ <- deleteUser(request)
          } yield ()
        )
    }
}

Once we have that, defining our routes can now have types reflecting their authentication, and we can package up our authentication check in one central place. Seems kinda nice!

Generically Contextual Routes

In fact, nothing in the above strictly depended on Authenticated. We could write for once and for all a ContextualRoutes handler, and specialize to the case of authenticated.

object ContextualRoutes {
  def of[F[_]: Monad, G[_]: Comonad](
    validator: Request[F] => G[Request[F]]
    )(
      route: PartialFunction[
        Request[F],
        Cokleisli[G, Request[F], OptionT[F, Response[F]]]
      ]
    ): Kleisli[OptionT[F, *], Request[F], Response[F]] =
    Kleisli(
      req => route(req).run(validator(req))
    )
}
object AuthenticatedRoutes {
  def of[F[_]: Monad] = ContextualRoutes[F, Authenticated].of(_)(_)
}

With this, one could then have as many different types of context as one needed - perhaps corresponding to different authentication standards, sources of evidence, or really anything else you might want to capture as a contextual detail. Maybe it could be API client versions, user roles or authorization claims, who knows.

The last ingredient you'd need would be a way to combine different types of contextural routes¹⁴ but I'll leave that as a direction you can think about on your own.

Conclusion

Comonads can be interesting when trying to capture generically the concept of a "context" a value can be couched in.

In this blog post, we explored a couple ideas around Comonads and how we might use them to capture Authenticated status in a type for our routes, just to see what we could do.

I'm not sure how ergonomic these ideas are in practice, but I think they're interesting. Hopefully, you did as well.

Thanks for reading!

def to[A](authed: Authenticated[A]): (Evidence, A) =
  (authed.evidence, authed.value)

def fro[A](t: (Evidence, A)): Authenticated[A] =
  new Authenticated(t._1, t._2) {}

/scala/ /functional-programming/ /comonad/ /design/ /musings/