shapeless — an exploration of generic programming in Scala

Posted: 19 Dec 2011
by: Miles Sabin

Miles Sabin — 19 December 2011 [edit]

shapeless is an exploration of generic (aka polytypic) programming in Scala derived from the various talks I’ve given over the course of 2011 on implementing scrap your boilerplate and higher rank polymorphism in Scala. It’s published under the Apache 2.0 licence and hosted on github — fork it and have a play.

In the new year I’ll be posting a (long overdue) series of articles here on the implementation techniques used — heavily type class based, with essential use of dependent types at various junctures, which together enable the relatively smooth encoding of type level functions. In the meantime you’ll find Olivera, Moors and Odersky Type Classes as Objects and Implicits useful background material.

Selected highlights of shapeless include …

A new encoding of polymorphic function values which optionally supports type specific cases, and which is interoperable with Scala’s ordinary monomorphic function values.

// choose is a function from Sets to Options
object choose extends (Set ~> Option) {
  def default[T](s: Set[T]) = s.headOption
}

// choose is convertible to an ordinary monomorphic function value
val lo = List(Set(1, 3, 5), Set(2, 4, 6)) map choose
lo == List(Option(1), Option(2))

// size is a function from values of arbitrary type to a 'size' which
// is  defined via type specific cases
object size extends (Id ~> Const[Int]#λ) {
  def default[T](t: T) = 1
}
implicit def sizeInt = size.λ[Int](x => 1)
implicit def sizeString = size.λ[String](s => s.length)
implicit def sizeList[T] = size.λ[List[T]](l => l.length)
implicit def sizeOption[T](implicit cases: size.λ[T]) =
  size.λ[Option[T]](t => (t map size).getOrElse(0))
implicit def sizeTuple[T, U]
  (implicit st: size.λ[T], su: size.λ[U]) =
    size.λ[(T, U)](t => size(t._1)+size(t._2))

size(23) == 1
size("foo") == 3
size((23, "foo")) == 4

An implementation of Scrap your Boilerplate with Class which provides generic map and fold operations over arbitrarily nested data structures,

val nested = List(Option(List(Option(List(Option(23))))))

val succ = everywhere(inc)(nested)
succ == List(Option(List(Option(List(Option(24))))))

A Typeable type class which provides a type safe cast operation,

val a: Any = List(Vector("foo", "bar", "baz"), Vector("wibble"))

val lvs: Option[List[Vector[String]]] = a.cast[List[Vector[String]]]
lvs.isDefined == true

val lvi: Option[List[Vector[Int]]] = a.cast[List[Vector[Int]]]
lvi.isEmpty == true

The mother of all Scala HList’s which, amongst other things, is covariant,

trait Fruit
case class Apple() extends Fruit
case class Pear() extends Fruit

type FFFF = Fruit :: Fruit :: Fruit :: Fruit :: HNil
type APAP = Apple :: Pear :: Apple :: Pear :: HNil

val a: Apple = Apple()
val p: Pear = Pear()

val apap: APAP = a :: p :: a :: p :: HNil
val ffff: FFFF = apap  // APAP <: FFFF

It has a map operation, applying a polymorphic function value (possibly with type specific cases) across its elements. This means that it subsumes both typical HList’s and also KList’s (HList’s whose elements share a common outer type constructor),

type SISS = Set[Int] :: Set[String] :: HNil
type OIOS = Option[Int] :: Option[String] :: HNil

val sets: SISS = Set(1) :: Set("foo") :: HNil
val opts: OIOS = sets map choose
opts == Option(1) :: Option("foo") :: HNil

It has a zipper for traversal and persistent update,

val l = 1 :: "foo" :: 3.0 :: HNil

val l2 = l.toZipper.right.put("wibble", 45).toHList
l2 == 1 :: ("wibble", 45) :: 3.0 :: HNil

val l3 = l.toZipper.right.delete.toHList
l3 == 1 :: 3.0 :: HNil

val l4 = l.toZipper.last.left.insert("bar").toHList
l4 == 1 :: "foo" :: "bar" :: 3.0 :: HNil

It has a unify operation which converts it to an HList of elements of the least upper bound of the original types,

val ffff = apap.unify // type inferred as FFFF

It supports conversion to an ordinary Scala List of elements of the least upper bound of the original types,

val lf = apap.toList  // type inferred as List[Fruit]
lf == List(a, p, a, p)

And it has a Typeable type class instance, allowing, eg. vanilla List[Any]’s or HList’s with elements of type Any to be safely cast to precisely typed HList’s,

// discard precise typing
val ffff: FFFF = apap.unify

// reestablish precise typing
val apap2: Option[APAP] = ffff.cast[APAP]
apap2.get == apap

These last three features make this HList dramatically more practically useful than HList’s are typically thought to be — normally the full type information required to work with them is too fragile to cross subtyping or I/O boundaries. This implementation supports the discarding of precise information where necessary (eg. to serialize a precisely typed record after construction), and its later reconstruction (eg. a weakly typed deserialized record with a known schema can have it’s precise typing reestabilished).

Conversions between tuples and HList’s, and between ordinary Scala functions of arbitrary arity and functions which take a single corresponding HList argument,

// Round trip from tuple to HList and back
val t1 = (23, "foo", 2.0, true)

val l1 = t1.hlisted
h1 == 23 :: "foo" :: 2.0 :: true :: HNil

val t2 = l1.tupled
t1 == t2

One application of this is the liftO function which lifts an ordinary function of arbitrary arity into Option.

// Lift these ordinary Scala function values into Option
val sum: (Int, Int) => Int = _ + _
val prd: (Int, Int, Int) => Int = _ * _ * _

// Nb. liftO abstracts over the arity of its function arguments

// (Option[Int], Option[Int]) => Option[Int]
val sumO = liftO(sum)

// (Option[Int], Option[Int], Option[Int]) => Option[Int]
val prdO = liftO(prd)

val s1 = sumO(Some(1), Some(2))
s1 == Option(3)

val s2 = sumO(Some(1), None)
s2 == None

val p1 = prdO(Some(2), Some(3), Some(4))
p1 == Option(24)

val p2 = prdO(Some(2), None, Some(4))
p2 == None

The library is targetted at Scala 2.10-SNAPSHOT by default, but currently should build against Scala 2.9.1.final with the -Ydependent-method-types switch enabled. I make no promises that it’ll continue to build with 2.9.x, or even vanilla Scala 2.10-SNAPSHOT — in 2012 I plan to investigate, amongst other things, what can be done with singleton types for literal values — at a minimum they would make the clunky encoding of type level natural numbers redundant, and might enable a whole lot more.

Fork it, kick the tires over the holiday and let me know how you get on!