Type level functions consume types and produce types. This allows us to tell the compiler exactly what we want in our code that errors may be caught at compile time rather than at later stages in our product deployment cycle. The true power of this approach lies in the fact that with Scala no application can be produced without compilation. No matter how undisciplined a developer may be, she cannot skip compilation. Moving error checking into compilation gives us more confidence in the performance of our binary than confidence gained by any other means. In short, when there is a failure in production we always ask "were the tests run?" but never do we ask "was it compiled?"
A Basic Zipper
Here we have a zipper.
def zipper[A, B, C]( a: List[A], b: List[B], c: List[C] ): List[(A, (B, C))] = a.zip(b.zip(c))
From previous posts in this series we know this can be generalized with a type class. Let's exercise this muscle immediately.
trait Zip[F[_]]{
def apply[A, B](a: F[A], b: F[B]): F[(A, B)]
}
def zipper[F[_]: Zip, A, B, C](
a: F[A], b: F[B], c: F[C]): F[(A, (B, C))] = {
val F = implicitly[Zip[F]]
F(a, F(b, c))
}
This is nicer than the first version but it is still super restrictive. It only works for zipping exactly 3 values. If we want to zip 2 or 4 or 70 values, we are out of luck! We saw how the shapeless HList allowed us to compose an arbitrary number of arbitrary types into a single type. Let's try to use the same kinds of methods here to produce a zipper of arbitrary arity.
Step 1 - Simplify as much as is possible
We will simplify a zipper to the purest form we can. The purest zipper takes two instances of a particular type constructor and produces a single instance of that type constructor on a pair. Let's write that.
def zipper[F[_]: Zip, H, T](
h: F[H], t: F[T]): F[(H, T)] = {
val F = implicitly[Zip[F]]
F(h, t)
}
Now, we don't need separate functions for different arity versions of a zipper. We can simply call this function recursively to produce the desired result.
val (list1, list2, list3, list4, list5, list6) = ...
implicit val ZipList = new Zip[List]{
override def apply[A, B](
a: List[A], b: List[B]): List[(A, B)] = a.zip(b)
}
val with2 = zipper(list1, list2)
val with3 = zipper(list1,
zipper(list2, list3))
val with6 = zipper(list1,
zipper(list2,
zipper(list3,
zipper(list4,
zipper(list5, list6)))))
If we recall the shapeless HList code learned to read, we see the same pattern here of a recursive type being produced from recursive calls. This can be done in the compiler using implicits.
Step 2 - Replace explicit recursion with implicit
implicit def zipper[F[_]: Zip, H, T](implicit
h: F[H], t: F[T]): F[(H, T)] = {
val F = implicitly[Zip[F]]
F(h, t)
}
This is the same code just the keyword implicit is placed in two locations. In scala we can promote an explicit call to an implicit call simply by adding a keyword. We inform the inputs with implicit so the compiler knows to find the head and tail by itself. We inform the function with implicit so the compiler knows to call the function implicitly if a value of the necessary type is not found.
We communicate our intent to the compiler with implicits and types. Type aliases help simplify business logic.
type F[A] = List[A] type Result = F[ (Int, (Long, (String, (Double, (Float, Array[Byte]) ))))]
To tell the compiler which values it can use during the application of functions we inform the values as implicit
implicit val list1: List[Int] = ??? implicit val list2: List[Long] = ??? implicit val list3: List[String] = ??? implicit val list4: List[Double] = ??? implicit val list5: List[Float] = ??? implicit val list6: List[Array[Byte]] = ???
The implicitly function tells the compiler what it needs to execute.
implicitly[Result]
And that's it! The compiler assembles the recursive calls for us. No more errors from placing things in the wrong order; refactoring is as simple as rearranging the order of the types in our alias Result. One change on one line propagates throughout the entire code base automatically.
Why stop at Tuple2?
There is nothing here that requires that a tuple be used. In fact, the only thing we need is a type constructor of arity 2. We can express as
trait ZipG[F[_], G[_, _]]{
def apply[A, B](a: F[A], b: F[B]): F[G[A, B]]
}
implicit def zipper[F[_], G[_, _], H, T](implicit
F: ZipG[F, G], h: F[H], t: F[T]): F[G[H, T]] = {
F(h, t)
}
And we can zip Tuple2s or Eithers by creating type class instances
implicit val zipListTuple2 = new ZipG[List, Tuple2]{
override def apply[A, B](
a: List[A], b: List[B]): List[(A, B)] = a.zip(b)
}
implicit val zipListEither = new ZipG[List, Either]{
override def apply[A, B](
a: List[A], b: List[B]): List[Either[A, B]] =
for{a <- a; b <- b}yield{
if(a.toString.size < b.toString.size) Left(a)
else Right(b)
}
}
For Tuple2 we have business logic like
type F[A] = List[A] type Result = F[ (Int, (Long, (String, (Double, (Float, Array[Byte]) ))))] implicit val list1: List[Int] = ??? implicit val list2: List[Long] = ??? implicit val list3: List[String] = ??? implicit val list4: List[Double] = ??? implicit val list5: List[Float] = ??? implicit val list6: List[Array[Byte]] = ??? implicitly[Result]
This is the same as before. Commonly, further abstractions at the type level have little or no effect on code at the value level. Abstractions should allow the code to be more expressive than it was prior to the abstraction exercise never less expressive.
Changing our business logic to use Either as our Zipping class is simple
type F[A] = List[A] type Result = F[ Either[Int, Either[Long, Either[String, Either[Double, Either[Float, Array[Byte]] ]]]]] implicit val list1: List[Int] = ??? implicit val list2: List[Long] = ??? implicit val list3: List[String] = ??? implicit val list4: List[Double] = ??? implicit val list5: List[Float] = ??? implicit val list6: List[Array[Byte]] = ??? implicitly[Result]
This is very powerful. By changing our type aliases, we were able to entirely change the meaning of our business logic without complex refactorings. As long as there are the correct type classes in implicit scope, the business logic need not be bothered by those implementation details.
What we have here is a sort of data pipeline and writer. Now that we have formatted data that we can work with in code, how do we present that data to an operator? Next, we'll write a reader for our types.