by Paul Heymann on Jun 15, 2018
technical
In this blog post, I will show you how to leverage Scala’s type system to derive an HTTP client function from a single type. This will also be the story of how I started to work on Typedapi which is basically the attempt to bring Haskell’s Servant to Scala.
For everyone not knowing Servant, it is a library which lets you define your web apis as types and derives the client and server functions from it. When I saw it for the first time while working on a pet project I immediately loved the idea. Creating web server and clients this way reduces your code to a mere type, you get extra type safety and you can use the api types as contracts between your server and its clients.
I couldn’t find any viable alternative in Scala at the time and decided to build it on my own. But I just wanted to start with a single feature to not overwhelm myself and abandon the project after a short time. Therefore, I set out to make Scala able to derive a client function from a single api type, as we will do in this post.
Let’s start with an example we will use later on to ease understanding. Consider the following api:
GET /users/:name?minAge=:age -> List[User]
It only consists of a single endpoint which returns a list of Users:
final case class User(name: String, age: Int)
with a given name: String. Furthermore, you filter the resulting users by their age: Int. Our big goal is to end up with a function which is derived from a type-level representation of our endpoint:
(name: String, minAge: Int) => F[List[User]]
Question: how do you represent the above api as a type in Scala? I think the best way is to break it apart and try to find type-level representations for each element. After that, we “just” merge them together.
When we take a closer look at our endpoint we see that it consists of:
GET to identify which kind of operation we want to do and which also describes the expected return type/users:nameminAge=[age]Or in other words, just a plain HTTP definition of a web endpoint. Now that we know what we are working with let’s try and find a type-level representation.
But how do you transform a value-level information as a type? First of all, the value has to be known at compile time which leaves us with literals. If we would work with Dotty we could leverage a concept called literal type:
type Path = "users"
But since we want to stay in Vanilla Scala this will not work. We have to take another route by using a tool probably every developer has to use when it comes to working on the type-level called shapeless. It has this nifty class Witness which comes with an abstract type T. And T is exactly what we need here as it transforms our literals into types.
import shapeless.Witness
val usersW = Witness("users")
But this isn’t a pure type declaration, you will say. And you are right, but right now there is no other way in Scala. We have to go the ordinary value road first to create our types.
Now that we know how to get a type representation from a String which describes our path we should clearly mark it as a path element:
sealed trait Path[P]
type users = Path[usersW.T]
That’s it. That is the basic concept of how we can describe our apis as types. We just reuse this concept now for the remaining elements like the segment.
val nameW = Witness('name)
sealed trait Segment[K, V]
type name = Segment[nameW.T, String]
Do you see how we included the segment’s identifier in the type? This way we are not only gain information about the expected type but also what kind of value we want to see. By the way, I decided to use Symbols as identifiers, but you could also switch to String literals. The remaining definitions look pretty similar:
val minAgeW = Witness('minAge)
sealed trait Query[K, V]
type minAge = Query[minAgeW.T, Int]
sealed trait Method
sealed trait Get[A] extends Method
Here, A in Get[A] represents the expected result type of our api endpoint.
Now that we know how to obtain the types of our api elements we have to put them together into a single type representation. After looking through shapeless’s features we will find HLists, a list structure which can store elements of different types.
import shapeless.{::, HNil}
type Api = Get[List[User]] :: users :: name :: minAge :: HNil
Here you go. Api is an exact representation of the endpoint we defined at the beginning. But you don’t want to write Witness and HLists all the time so let’s wrap it up into a convenient function call:
def api[M <: Method, P <: HList, Q <: HList, Api <: HList]
(method: M, path: PathList[P], queries: QueryList[Q])
(implicit prepQP: Prepend.Aux[Q, P, Api]): ApiTypeCarrier[M :: Api] = ApiTypeCarrier()
val Api = api(Get[List[User]], Root / "users" / Segment[String]('name), Queries.add(Query[Int]('minAge)))
Not clear what is happening? Let’s take a look at the different elements of def api(...):
method should be obvious. It takes some method type.PathList is a type carrier with a function def /(...) to concatenate path elements and segments. In the end, PathList only stores the type of an HList and nothing more.final case class PathList[P <: HList]() {
def /[S](path: Witness.Lt[S]): PathList[S :: P] = PathList()
...
}
val Root = PathList[HNil]()
QueryList.HLists types into a single one. Shapeless comes again with a handy type class called Prepend which provides us with the necessary functionality. Two HList types go in, a single type comes out. And again, we use a type carrier here to store the api type.Whoho, we did it. One thing we can mark as done on our todo list. Next step is to derive an actual client function from it.
So far we have a type carrier describing our api as type:
ApiTypeCarrier[Get[List[User]] :: Query[minAgeW.T, Int] :: Segment[nameW.T, String] :: usersW.T :: HNil]
Now we want to transform that into a function call (name: String, minAge: Int) => F[List[User]]. So what we need is the following:
All information are available but mixed up and we need to separate them. Usually, when we work with collections and want to change their shape we do a fold and alas shapeless has type classes to fold left and right over an HList. But we only have a type. How do we fold that?
What we want is to go from Api <: HList to (El <: HList, KIn <: HList, VIn <: HList, M, Out) with:
El al the elements in our api: "users".type :: SegmentInput :: QueryInput :: GetCall :: HNilKIn the input key types: nameW.T :: minAgeW.T :: HNilVIn the input value types: String :: Int :: HNilGetCallOut: List[User]Here, we introduced new types SegmentInput and QueryInput which act as placeholders and indicate that our api has the following inputs. This representation will come in handy when we construct our function.
Now, how to fold on the type-level? The first step, we have to define a function which describes how to aggregate two types:
trait FoldLeftFunction[In, Agg] { type Out }
That’s it. We say what goes in and what comes out. You need some examples to get a better idea? Here you go:
implicit def pathTransformer[P, El <: HList, KIn <: HList, VIn <: HList, M, Out] =
FoldLeftFunction[Path[P], (El, KIn, VIn, M, Out)] { type Out = (P :: El, KIn, VIn, Out) }
We expect a Path[P] and intermediate aggregation state (El, KIn, VIn, M, Out). We merge the two by adding P to our list of api elements. The same technique is also used for more involved aggregations:
implicit def segmentTransformer[K <: Symbol, V, El <: HList, KIn <: HList, VIn <: HList, M, Out] =
FoldLeftFunction[Segment[K, V], (El, KIn, VIn, M, Out)] { type Out = (SegmentInput :: El, K :: KIn, V :: VIn, Out) }
Here, we get some Segment with a name K and a type V and an intermediate aggregation state we will update by adding a placeholder to El, the name to KIn and the value type to VIn.
Now that we can aggregate types we need a vehicle to traverse our HList type and transform it on the fly by using our FoldLeftFunction instances. I think yet another type class can help us here.
trait TypeLevelFoldLeft[H <: HList, Agg] { type Out }
object TypeLevelFoldLeft {
implicit def returnCase[Agg] = new TypeLevelFoldLeft[HNil, Agg] {
type Out = Agg
}
implicit def foldCase[H, T <: HList, Agg, FfOut, FOut](implicit f: FoldLeftFunction.Aux[H, Agg, FfOut],
next: Lazy[TypeLevelFoldLeft.Aux[T, FfOut, FOut]]) =
new TypeLevelFoldLeft[H :: T, Agg] { type Out = FOut }
}
The above definition describes a recursive function which will apply the FoldLeftFunction on H and the current aggregated type Agg and continues with the resulting FfOut and the remaining list. And before you bang your head against the wall for hours until the clock strikes 3 am, like I did, a small hint, make next lazy. Otherwise, Scala is not able to find next. My guess is that Scala is not able to infer next, because it depends on FfOut which is also unknown. So we have to defer next’s inference to give the compiler some time to work.
And another hint, you can start with Unit as the initial type for your aggregate.
We folded our api type into the new representation making it easier now to derive a function which collects all the data necessary to make a request.
// path to our endpoint described by Path and Segment
type Uri = List[String]
// queries described by Query
type Queries = Map[String, List[String]]
VIn => (Uri, Queries)
This function will form the basis of our client function we try to build. It generates the Uri and a Map of Queries which will be used later on to do a request using some HTTP library.
By now, you should be already comfortable with type classes. Therefore, it shouldn’t shock you that I will introduce yet another one to derive the above function.
trait RequestDataBuilder[El <: HList, KIn <: HList, VIn <: HList] {
def apply(inputs: VIn, uri: Uri, queries: Queries): (Uri, Queries)
}
Instances of this type class update uri and queries depending on the types they see. For example, if the current head of El is a path element we prepend its String literal to uri. Just keep in mind to reverse the List before returning it.
implicit def pathBuilder[P, T <: HList, KIn <: HList, VIn <: HList](implicit wit: Witness.Aux[P], next: RequestDataBuilder[T, KIn, VIn]) =
new RequestDataBuilder[P :: T, KIn, VIn] {
def apply(inputs: VIn, uri: Uri, queries: Queries): (Uri, Queries) =
next(inputs, wit.value.toString() :: uri, queries, headers)
}
Or if we encounter a query input we derive the key’s type-literal, pair it with the given input value and add both to queries:
implicit def queryBuilder[K <: Symbol, V, T <: HList, KIn <: HList, VIn <: HList](implicit wit: Witness.Aux[K], next: RequestDataBuilder[T, KIn, VIn]) =
new RequestDataBuilder[QueryInput :: T, K :: KIn, V :: VIn] {
def apply(inputs: V :: VIn, uri: Uri, queries: Queries): (Uri, Queries) =
next(inputs.tail, uri, Map(wit.value.name -> List(inputs.head.toString())) ++ queries)
}
The other cases are looking quite similar and it is up to the interested reader to find the implementations.
What we end up with is a nested function call structure which will take an HList and returns the uri and queries.
val builder = implicitly[RequestDataBuilder[El, KIn, VIn]]
val f: VIn => (Uri, Queries) = input => builder(input, Nil, Map.empty)
"joe" :: 42 :: HNil => (List("users", "joe"), Map("minAge" -> List("42")))
Here, "joe" and 42 are our expected inputs (VIn) which we derived from the segments and queries of our Api.
We have all the data we need to make an IO request but nothing to execute it. We change that now. By adding an HTTP backend. But we don’t want to expose this implementation detail through our code. What we want is a generic description of a request action and that sounds again like a job for type classes.
trait ApiRequest[M, F[_], C, Out] {
def apply(data: (Uri, Queries), client: C): F[Out]
}
We have to specialize that for the set of methods we have:
trait GetRequest[C, F[_], Out] extends ApiRequest[GetCall, C, F, Out]
...
val request = implicitly[ApiRequest[GetCall, IO, C, List[User]]]
val f: VIn => IO[List[User]] =
input => request(builder(input, Nil, Map.empty), c)
Let’s say we want http4s as our backend. Then we just have to implement these traits using http4s functionality.
We have a bunch of type classes which in theory do a request, but so far they are completely useless. To make a working piece of code out of it we have to connect them.
def derive[Api <: HList, El <: HList, KIn <: HList, VIn <: HList, M, Out, F[_], C]
(api: ApiTypeCarrier[Api], client: C)
(implicit fold: Lazy[TypeLevelFoldLeft.Aux[Api, Fold], (El, KIn, VIn, M, Out)]
builder: RequestBuilder[El, KIn, VIn],
request: ApiRequest[M, F, C, Out]): VIn => F[Out] = vin => request(builder.apply(vin, List.newBuilder, Map.empty), client)
The first approach gives us the desired function. It transforms our api type into a (El, KIn, VIn, Method, Out) representation, derives a function to collect all data to do a request, and finds an IO backend to actually do the request. But it has a major drawback. You have to fix F[_] somehow and the only way is to set it explicitly. But by doing that you are forced to provide definitions for all the type parameters. Furthermore, this function isn’t really convenient. To use it you have to create and pass an HList and as we said before, we don’t want to expose something like that.
To fix the first problem we simply add a helper class which moves the step of defining the higher kind F[_] to a separate function call:
final class ExecutableDerivation[El <: HList, KIn <: HList, VIn <: HList, M, O](builder: RequestDataBuilder[El, KIn, VIn], input: VIn) {
final class Derivation[F[_]] {
def apply[C](client: C)(implicit req: ApiRequest[M, C, F, O]): F[O] = {
val data = builder(input, List.newBuilder, Map.empty, Map.empty)
req(data, cm)
}
}
def run[F[_]]: Derivation[F] = new Derivation[F]
}
Making a function of arity Length[VIn] out of Vin => F[O]is possible by using shapeless.ops.function.FnFromProduct.
When we apply both solutions we end up with:
def derive[H <: HList, Fold, El <: HList, KIn <: HList, VIn <: HList, M, Out]
(apiList: ApiTypeCarrier[H])
(implicit fold: Lazy[TypeLevelFoldLeft.Aux[H, Unit, (El, KIn, VIn, M, Out)]],
builder: RequestDataBuilder[El, KIn, VIn],
vinToFn: FnFromProduct[VIn => ExecutableDerivation[El, KIn, VIn, M, Out]]): vinToFn.Out =
vinToFn.apply(input => new ExecutableDerivation[El, KIn, VIn, M, Out](builder, input))
I already hear the “your function signature is so big …” jokes incoming, but this is basically what we will (and want to) end up with when doing type-level programming. In the end, our types have to express the logic of our program and that needs some space.
But finally, we can say we did it! We convinced the Scala compiler to derive a client function from a type. Let’s have a look at our example to see how it works.
import cats.effect.IO
import org.http4s.client.Client
val Api = api(Get[List[User]], Root / "users" / Segment[String]('name), Queries.add(Query[Int]('minAge)))
val get = derive(Api)
get("joe", 42).run[IO](Client[IO]) // IO[List[User]]
When you take a closer look at the code above you will see that we were able to move most of the heavy lifting to the compiler or shapeless therefore reducing our code to a relatively small set of “simple” type classes. And when literal types are in thing in Scala we can also remove most of the boilerplate necessary to create our api types.
This, again, shows me how powerful Scalas type system is and how much you can gain when you embrace it.
Now that we are able to derive a single client function from a type we should also be able to do the same for a collection of api types. And if we are already on it, let’s add server-side support. Or … you just use Typedapi. It already comes with the following features:
