# Comonads and Authentication as Context

## Table of contents

`> wc -w`

~ 3059
Reading time estimate ~ 16 minutes

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^{1}. 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^{2}. 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^{3}?

### 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^{4}.

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^{5}.

#### Dualizing `flatMap`

Alright how would we draw `flatMap`

, very non-rigorously^{6}? 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`

^{7}.

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`

.

`Comonad`

s

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! `Monad`

s are very welcoming but hold their values tightly, while `Comonad`

s 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^{8}.

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^{9}).

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 `coflatMap`

ing 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)
```

`Comonad`

s, in principle, allow a similar but dual affordance^{10}!

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^{11}:

```
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`

^{12}. 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^{13}.

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^{14} but I'll leave that as a direction you can think about on your own.

## Conclusion

`Comonad`

s 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 `Comonad`

s 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!

^{1}

This is, afterall, not an exposition of category theory specifically!

^{2}

There are certainly enough and I'm not going to punish the world with yet one more take. You'll find your way, I'm sure.

^{3}

You might wonder, why do this? What could it get you? All I can say is that it's intellectually interesting. More broadly, comonads have real uses in mathematics and in the modeling of programming semantics. There's a real interesing line of thought on comonadic user interface modeling, for example.

^{4}

Can you think of a way to fix `List`

so that it can implement `extract`

? Hint: It's not subtle, you just need to make it so you can *always* get a value out of it.

^{5}

Unless, of course, yes, you were "very clever" and wrote an implicit conversion (or relied on some insane abstruse way of bullying the JVM). But you wouldn't do that? Right? You love yourself, and your fellow humans, don't you? You wouldn't just hurt someone for no reason? Right. So why are we talking about that?

^{6}

Really, you have to draw a pretty big diagram to characterize `flatMap`

, because you have to capture the laws involved, and so forth. But here I wnat to just get to the intution of what the operation is, what it's trying to mean without thinking too hard about the making it rigorous, so I'm eliding a lot of really important detail. If this offends you, I totally get that, but you might be the wrong audience for what I'm trying to do! Which is also totally fine, thanks for giving my writing a shot.

^{7}

Don't worry, we'll get to it.

^{8}

Naturally, an alternative design is just to make it very hard to inhabit the `Evidence`

type, and rely on the validators producing *that* type to protect our contract, but I think it's clearer in this restricted context to design it this way.

^{9}

One way you can think about that is that the instance is basically isomorphic to the one provided for `Tuple2[Evidence, A]`

. You only need to map back and forth between the tuple representation and our case class as necessary, like:

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

^{10}

There was actually a proposal for this at one point, and you can read the cofor proposal here with a related PR for comonadic comprehensions here. Both are based on this paper on codo for Haskell written by Dominic Orchard and Alan Mycroft.

^{11}

If you are curious why this `cofor`

returns a function while `for`

straight returns a value, I encourage you to read the paper in the previous footnote. It is essentially because comonads work with functions on structured input, while monads work with functions producing structured output, and that duality drives the two to be modeled with different types of computations.

^{12}

Notably, `Cokleisli`

is not just an empty concept! If `F`

is a `Comonad`

, then `Cokleisli[F, A, *]`

is a `Monad`

! This means you can translate our `cofor`

computations above into nested `for`

comprehensions, and in this way, to a certain degree, leverage the ergonomics of `for`

in a `Comonad`

ic context since we don't actually have `cofor`

support in Scala. This would be useful in combining different subcomputations into handlers.

^{13}

Having been out of the scene for quite a bit and never used `http4s`

all that seriously, I actually wasn't aware they had a facility for authenticated routes with some similar ideas until the writing of this post. You can read all about their authenticated routes here. Pretty neat.

^{14}

You don't really actually need to think about context-free routes from a logical point of view, since they are a special case. The `type Id[A] = A`

actually implements `Comonad`

!