Jan 5, 2024 Type class constraints in object algebras

Empower your object algebras

It’s been a while since Julien Richard Foy has given a talk about object algebras. Meanwhile he has been busy building endpoint4s using this technique.

You can view the video here

In this blog post I would like to go over type class constraints on object algebras which make object algebras more powerful. I’ve build a toy library in 2018 myself using this technique which is similar to endpoint4s or tapir

What is an object algebra?

An example is to model the abstract HttpResponse of an endpoints library, this might look like this

trait HttpResponse[A] {
  type HttpResponse[A]
  type HttpResponseBody[A]
  type HttpResponseHeaders[A]

  def response[A, B](statusCode: HttpStatus, description: String, headers: HttpResponseHeaders[A] = emptyResponseHeaders, entity: HttpResponseEntity[B])(implicit T: Tupler[A, B]): HttpResponse[T.Out]

}

This is pretty abstract, the abstract types are implemented in the interpreters of the server, client and documentation. The response function accepts these abstract types, which will output a new type. Tupler concatenates two types yielding a T.Out I’ve implemented this in Scala 2, in Scala 3 you could do this with probably more elegantly

Type class constraints on abstract types

Now next to the abstract types you could add type class constraints to these types as they match the kind * -> *

What type classes could you possibly apply to our types? Well, for example Invariant from cats

Invariant

A simplified definition is

trait Invariant[F[_]] {
  def imap[A, B](fa: F[A])(f: A => B)(g: B => A): F[B]
}

This gives us imap which is a combination of a map and contramap. This fits an isomorphism which allows you to convert, for example, from Celsius to Fahrenheit. But also, for example, from a case class Person(name: String, age: Int) to heterogeneous representation String :: Int :: HNil. This is quite handy when you want to map inputs or outputs in your EDSL HTTP library to case classes and such.

An Invariant functor however does not account for any failure on decoding data. I’ve looked for a functor which did this, but at that time it wasn’t there and I created a Partial type class without any axioms

Partial

The definition of Partial looks like this

trait Partial[F[_]] {
  def pmap[A, B](fa: F[A])(f: A => Attempt[B])(g: B => A): F[B]
}

This looks pretty similar to Invariant except that the map part now returns an Attempt which is an error type. Partial can be applied to parts of the HTTP algebra where decoding can fail. For example query strings, segments, headers, etc.

CoCartesian

Another type class I invented myself is a dual of Cartesian which is in cats. It’s defined as:

trait CoCartesian[F[_]] {
  def sum[A, B](fa: F[A], fb: F[B]): F[Either[A, B]]
}

What do I mean with dual? In category theory you have products and coproducts. A product is the combination of two things which end up as a tuple. The dual to a product is a coproduct which is the combination of two things which is either one of these. That’s what been modeled with the CoCartesian type class.

This works together well with the Invariant type class. You have the following isomorphisms:

• Product: for nested tuples (constructed with the Cartesian type classes) like (A, (B, (C, D))) you can flatten them to a heterogeneous variant A :: B :: C :: D :: HNil which can in turn be translated to a case class
• Coproduct: for a nested either (constructed with the CoCartesian type class) like Either[A, Either[B, Either[C, D]]] you can flatten them to union variant in shapeless or Scala 3 like A | B | C | D which is isomorphic to an algebraic data type

Where is this used? In the HTTP response, where an endpoint could return multiple responses like an error or an actual response.

http4s server

implicit val httpResponseCocartesian: CoCartesian[Lambda[A => Function[A, Resp[F]]]] = new CoCartesian[Function[?, Resp[F]]] {
    override def sum[A, B](fa: Function[A, Resp[F]], fb: Function[B, Resp[F]]): Function[Either[A, B], Resp[F]] = {
      case Left(a)  => fa(a)
      case Right(b) => fb(b)
    }
  }

We implemented the CoCartesian on the http4s server part by a type lambda which returns a Function[A, Resp[F]]. This is in turn implemented in sum as the return type Function[Either[A, B], Resp[F]]. In the body you see that we just pattern match on the Either which delegates to the respective functions fa and fb

openapi docs

Implementing this for OpenAPI docs was pretty straightforward

implicit override val httpResponseCocartesian: CoCartesian[Lambda[A => OpenApiResponses]] = new CoCartesian[Lambda[A => OpenApiResponses]] {
  override def sum[A, B](fa: OpenApiResponses, fb: OpenApiResponses): OpenApiResponses = OpenApiResponses(fa.byStatusCode ++ fb.byStatusCode)
}

It’s basically a basic concatenation of a Scala collection

Conclusion

In this blog post I’ve gone over object algebra’s and type classes. Some of the concepts you may need to go over by yourself in the aforementioned links and videos. I think these are pretty powerful concepts to invent your own EDSL.

This could be foundational work for new libraries! Would be awesome to have an AsyncAPI library which makes documenting asynchronous API’s a bit easier.

However, note that working on new libraries takes a lot of effort and doing so involves marketing, a website, and having support by multiple contributors and companies. For that reason I’ve stopped working on libraries as it’s quite involving.