1. Overview
Generic programming allows us to write programs without code repetition. In Scala, the shapeless library introduces generic data types, type-classes, and operations by bringing value-level to type-level computation.
In this article, we’re going to learn some use cases of shapeless, but as generic programming is a broad topic, we won’t cover all of them.
2. Generic and Type-Level Programming
Generic programming is a way of programming for types and deferring the concrete types to be specified later.
For example, instead of writing IntList and StringList data types, we can write the generic List[T] data type and define some generic operations and combinators on that, like head, tail, map, and size. This helps us to write once and reuse multiple times with any data types:
val intList: List[Int] = List(1, 2, 3)
val stringList: List[String] = List("foo", "bar", "baz")
assert(intList.head == 1)
assert(stringList.head == "foo")
Shapeless extensively uses type-level programming to bring us generic data types and type classes to make generic programming easy. So, what is type-level programming? Type-level programming is a technique of encoding, in the type system, computations that are evaluated at compile-time.
When we bring information from value-level to type-level programming, the encoded logic will be checked at compile-time. This helps up to write bug-free programs, so if the program compiles, it works properly at runtime.
Let’s see what real problems we can solve with type-level programming. Assume we have a list of distinct types:
val list: List[Any] = List(1, 1.0, "One", false)So, what happens when we extract the first element of the list using the head function? We expect it returns the number 1 as an Int data type, but it returns that as Any, so we can’t access the type of the first element.
So, how can we do this properly in Scala? With the help of type-level programming, we can write a heterogeneous list that encodes member types to list definition. As this is a separate topic, we don’t dive deeply into this — instead, we can use shapeless’s HList. HList is a heterogeneous list that can preserve each element type at runtime.
There are lots of data types and type-classes that shapeless provides. In this article, we’ll only cover some of the more important ones like HList, Coproduct, Generic, LabelledGeneric, and polymorphic functions.
3. Generics
Every construction in category theory has a dual, the product type has a dual which is called coproduct (or sum type). In the shapeless library, the product construction is called HList and its dual is named Coproduct.
3.1. Heterogeneous List (HList)
HList is a combination of characteristics of both lists and tuples:
- Tuples are fixed lengths of elements of distinct types at compile time. Once we fix the arity of tuples, we will be stuck with them. On the other hand, each element of a tuple can be of different types but after definition, we can’t extend the arity of a tuple.
- Lists are variable-length sequences of elements all of the same type.
HList has combined features of tuples and lists. It captures the sequence of distinct types from tuples and captures the variable-length sequence of elements from lists. So, HList is a variable-length sequence of elements of distinct types:
import shapeless._
import HList._
val hlist = 1 :: 1.0 :: "One" :: false :: HNilHere, the type of the hlist is very different from the common List type in the standard collection library of Scala. Its type is Int :: Double :: String :: Boolean :: HNill. Strange! So, let’s decipher the meaning of this data type. Here is the definition of HList in shapeless:
sealed trait HList extends Product with Serializable
final case class ::[+H, +T <: HList](head : H, tail : T) extends HList
sealed trait HNil extends HList {
def ::[H](h : H) = shapeless.::(h, this)
}
case object HNil extends HNil
HList is a recursive data structure. Each HList is either an empty list (HNil) or a pair of H and T types, in which H (head) is an arbitrary type and T (tail) is another HList. In Scala, we can write any pair type like ::[H, T] in a more ergonomic way like H :: T, so the type of our hlist is either Int :: Double :: String :: Boolean :: HNill or ::[Int, ::[Double, ::[String, ::[Boolean, HNill]]]].
Similar to the standard library, we can call bunches of combinators on HList, including map, flatMap, head, and tail:
assert(list.head == 1)
assert(list.take(2) == 1 :: 1.0 :: HNil)
assert(list.tail == 1.0 :: "One" :: false :: HNil)HList has a lot of use cases. For example, by using Generic type-class, we can convert any case class to HList, and then we can iterate through the HList and write a CSV encoder for that.
3.2. Coproduct
In the standard library, we usually create a coproduct using sealed traits. For example, we can model a traffic light as:
selead trait TrafficLight
case class Green() extends TrafficLight
case class Red() extends TrafficLight
case class Yellow() extends TrafficLightAs we can see, each possible state of the traffic light is modeled as a separate case class, each one extending the sealed TrafficLight trait.
In shapeless, there’s a Coproduct data type that gives us more power for defining sum types. Coproduct in shapeless is also a recursive data structure like HList. Let’s model the traffic light with shapeless:
import shapeless._
object Green
object Red
object Yellow
type Light = Green.type :+: Red.type :+: Yellow.type :+: CNilNow, we can create a Red instance of Light type:
val light: Light = Coproduct[Light](Red)Now let’s check if the light is Red or not:
assert(light.select[Red.type] == Some(Red)
assert(light.select[Green.type] == None)There are lots of combinators and operations that we can run on this data type, such as head, tail, drop, and map.
4. Generic Type-Class
The Generic type-class can turn common product/coproduct types – concrete case class/tuple or sealed family of classes/traits – into corresponding generic types. The Generic trait has two methods, to and from:
trait Generic[T] extends Serializable {
type Repr
def to(t : T) : Repr
def from(r : Repr) : T
}The inner type Repr is the path-dependent type that contains the generic representation of type T. In other words, the Repr type depends on the type at which we instantiate the Generic. If we instantiate the Generic with a case class, the representation will be an HList, and if we instantiate it with a sealed family of classes, the representation will be a Coproduct.
4.1. Product Conversion (HList)
For every product type of T, like tuples or case classes, an instance of Generic type-class can convert that product type to HList with the to method:
import shapeless._
case class User(name: String, age: Int)
val user = User("John", 25)
val userHList = Generic[User].to(user)
assert(userHList == "John" :: 25 :: HNil)Also, we can convert the userHList back to the User case class:
val userRecord: User = Generic[User].from(userHList)
assert(user == userRecord)In this way, we can write a generic CSV serializer/deserializer that works on any product type. We can convert any case classes/tuples to HList and then serialize the HList to the CSV records and vice versa.
4.2. Coproduct Conversion
In the same way, we can convert the TrafficLight to the shapeless Coproduct:
val gen = Generic[TrafficLight]
val green = gen.to(Green())
val red = gen.to(Red())
val yellow = gen.to(Yellow())
Each family member of TrafficLight is encoded into nested Inl and Inr:
assert(green == Inl(Green()))
assert(red == Inr(Inl(Red())))
assert(yellow == Inr(Inr(Inl(Yellow()))))5. LabelledGeneric Type-Class
The Generic type-class doesn’t remember the field names of a case class, but the LabelledGeneric type-class does:
import shapeless._
import record._
val user = User("John", 25)
val userGen = LabelledGeneric[User]
val userLaballedRecord = userGen.to(user)The LabelledGeneric encodes field names as labels at a type-level computation:
assert(userLaballedRecord('name) == "John")
assert(keys() == 'name :: 'age :: HNil)This helps us to write a generic JSON encoder to convert any case class to a JSON AST. Lots of Scala JSON libraries like Circe, Argonount, and Play JSON do their automatic derivation with this approach.
6. Polymorphic Functions
Assume we have a List:
val list = List("foo", "bar")And let’s say we want to map through the list and determine the size of each element. How can we do it? We can map through the list with the length function:
val list: List[String] = List("foo", "bar")
def length: String => Int = _.length
val lengthList = list.map(length)The length is a monomorphic function because its input only works on strings. But what if we have a heterogeneous list:
val list = List(1, 2) :: "123" :: Array(1, 2, 3, 4) :: HNilEach item of this list has a different type, so what is the type of map function? Any => Int? Using Any is not a good idea. What if we could define a function that can accept List[Int] or String or Array[String] as an input? The output of this function is dependent on the input parameter types. Shapeless provides us a type called Poly for creating polymorphic functions.
Let’s write the length polymorphic function with Poly:
import shapeless._
object polyLength extends Poly1 {
implicit val listCase = at[List[Int]](i => i.length)
implicit val stringCase = at[String](d => d.length)
implicit val arrayCase = at[Array[Int]](d => d.length)
}The polyLength‘s apply method accepts different data types, and in the case of each, one of its implicit cases will be called:
assert(polyLength.apply(List(1, 2)) == 2)
assert(polyLength.apply("123") == 3)
assert(polyLength.apply(Array(1, 2, 3, 4)) == 4)
assert(list.map(polyLength) == 2 :: 3 :: 4 :: HNil)7. Conclusion
In this tutorial, we’ve learned what is generic programming in the context of type-level programming and how shapeless make it easy to write generic programs.
First, we learned how to create heterogeneous products and coproducts with shapeless by using HList and Coproduct data types.
Second, we got acquainted with Generic and LabelledGeneric type-classes, which help us to convert common product and coproduct types to corresponding generic ones and vice versa.
In the end, we learned what polymorphic functions are, and how the shapeless library provides us this machinery.
As always, the code is available over on GitHub.