Using type information to generate behaviour

More Typing,
Less Typing

Nick Pollard

Scotiabank

Scala has a powerful static type system

What is it good for?

• Validation
• Generating behaviour?

We use types to drive behaviour all the time

Typeclasses revisited

• An interface across types
• Common capability, varied behaviour by type
• Instances of the typeclass provide behaviour

trait Show[T] {
  def show(t: T): String
}

Implicit Search

• Scala uses implicit search to provide Typeclasses

def f[T](...)(implicit ev: Show[T])

def f[T : Show](...)

• Instances are defined as implicit values

implicit val showInt : Show[Int] = new Show[Int] {
  def show(i: Int): String = i.toString
}

• Can construct through implicit defs

implicit def list[T](implicit s: Show[T]): Show[List[T]] = 
  new Show[List[T]] {
    def show(ts: List[T]): String = 
      ts.map(s.show).mkString("(", ",", ")")
  }

When searching for an implicit, the compiler can chain successive implicit functions if it will produce the required type

• A breadth-first search
• Pretty much just Prolog

How can we handle more complex types with implicit defs?

An Algebra for Types

What is an Algebra

What does it mean to operate on types?

What is a type?

Types as sets

We can view types as sets of values

Now we can just steal set operators!

Product

• Cartesian product of sets
• Contain a value from A and one from B
• Equivalent to a Scala Tuple (A,B)
• (Bool,Int) = Set((false,0), (true,0), (false,1), (true,1)...)

Coproduct

• Also called a Sum type
• A disjoint Union - left and right types distinguished
• Equivalent to a scala Either or Scalaz \/
• Contain a value from A or from B
• Bool \/ Int = Set(false, true, -2,147,483,648, -2,147,483,647, ...)

We can express types in terms of operators

• Option[A] = () \/ A
• List[A] = () \/ (A, List[A])
• (A,B,C,D) = (A, (B, (C, D)))

What does this have to do with Typeclasses?

• We can model types as operators on simple types
• If we have
  • typeclass instances for simple types
  • implicit functions for type operators
• We can construct typeclass instances for arbitrary types

Enter Shapeless

Heterogenous Lists

• A list of heterogenous types
• Recursive product
• Equivalent to nested tuples (A, (B, (C, D)))

sealed trait HList
case class ::[H,T <: HList](head: H, tail: T) extends HList
case object HNil extends HList

type Example = Int :: String :: Double :: HNil

type Example = ::[Int,::[String,::[Double,HNil]]]

• All HList types are either HNil, or the product of a type and an HList
• All we need to generate arbitrary HList typeclasses:
  • A typeclass instance for HNil
  • An implicit function to create typeclasses for HCons

Shapeless Coproducts

• Similar to an HList - a list of heterogenous types
• Recursive coproduct
• Equivalent to nested Eithers A \/ (B \/ (C \/ D)))

sealed trait Coproduct
sealed trait :+:[H,T <: Coproduct] extends Coproduct
sealed trait CNil extends Coproduct

type Example = Int :+: String :+: Double :+: HNil

type Example = :+:[Int,:+:[String,:+:[Double,HNil]]]

Implicit parsers

trait Parsable[T] {
  def parser(open: String, sep: String, close: String) : Parser[T]
} 

We would like to be able to define a simple type hierarchy, and automatically parse that

 implicit def hnil: Parsable[HNil] = const[HNil](Pass map (_ => HNil)) 

 implicit def hcons[K <: Symbol, H, T <: HList](implicit 
						head: Lazy[Parsable[H]],
                                                tail: Lazy[Parsable[T]]
				): Parsable[FieldType[K,H] :: T] = 
    new Parsable[FieldType[K,H] :: T] {
      def parser(open: String, sep: String, close: String) =
        head.value.parser(open, sep, close) ~ P(sep) ~
          tail.value.parser(open, sep, close) map { 
            case (h,t) => field[K](h) :: t 
          }
    }

implicit def cnil : Parsable[CNil] = const[CNil](Fail)

implicit def ccons[K <: Symbol, H, T <: Coproduct](implicit 
                                          key: Witness.Aux[K] ,
					  head: Lazy[Parsable[H]],
                                          tail: Lazy[Parsable[T]]
                                 ): Parsable[FieldType[K,H] :+: T] =
  new Parsable[FieldType[K,H] :+: T] {
    def parser(open: String, sep: String, close: String) =
      P(P(key.value.name) ~ P(open) ~
        head.value.parser(open, sep, close).map(l => Inl(field[K](l))) ~
        P(close)) |
      P(tail.value.parser(open, sep, close).map(Inr(_)))
  }

implicit def project[T,U](implicit ev: LabelledGeneric.Aux[T,U], 
                                   p: Lazy[Parsable[U]]) : Parsable[T] =
  new Parsable[T] {
    def parser(open: String, sep: String, close: String) : Parser[T] =
       p.value.parser(open, sep, close) map ev.from
  }

Define our data types

sealed trait Source
case class Http(url: String) extends Source
case class DB(table: String) extends Source
case class Fallback(first: Source, second: Source) extends Source

Summon a parser

val parsable = the[Parsable[Source]]
val parser = parsable.parser("(", ",", ")")

Use it!

val str = "Fallback(Http(\"http://www.example.com\"),DB(\"table\"))" 
val result = parser.parse(str).get.value
assert(result === Fallback(Http("http://www.example.com"), DB("table")))

Thanks

Shapeless by Miles Sabin

Fastparse by Li Haoyi

Scala eXchange by Skills Matter

Check the video on skillshare

This presentation will soon be available on https://skillsmatter.com/conferences/6862-scala-exchange-2015#skillscasts

Slides available at http://nickpollard.github.io/typing/

Presentation by Nick Pollard @ Scotiabank

Questions

nick.pollard@scotiabank.com

@nick_enGB