pauldhoward/scala-at-the-sea-20180108.md

## scala-at-the-sea-20180108.md

      
    Raw
  

              scala-at-the-sea-20180108.md
            
          
    Scala at the Sea: 8 Jan 2019

Adam Rosien @arosien
Inner Product LLC
Can you read this? How about you over there? :thumbs_up:
Type-level programming

What is type-level programming?
Expressions, Types, Values


expression: has a type; are evaluated into values
1 + 1 => 2
val x = 1 + 1 // 2

type: exist at compile time
type Blah = Int
val x: Int = ???

value: has a type; exist at runtime
val x: Int = 2


What do we use to map between values and types?


values -> values?

functions

def foo(s: String): Int = s.length


value -> type?

every value has a type;

val x: Int = ???

dependent types: a type that depends on a value


type -> type?

type composition? There are different ways to compose types:

trait A
trait B
trait C extends A with B

trait F[A] // type constructor

trait Outer {
  type Inner
  class Foo
}

type -> value?

reflection?
implicitly is a good example, the only argument is a type

def implicitly[A](implicit a: A): A = a

typeclass (resolution)

aka ad-hoc polymorphism <--- fancy word alert
Example: How does a generic list sort its elements?
We could require all elements to be comparable, so that we can sort.

trait SortedList[A <: Comparable] extends List[A] {
  def sorted(): List[A] = ???
}

Instead, we require the comparison helper when sorted() is called.

trait List[A] {
  def sorted(help: (A, A) => Boolean): List[A] = ???
}

We then wrap the (A, A) => Boolean helper function in a trait Ordering[A], and require an implicit instance.

trait List[A] {
  def sorted(implicit help: Ordering[A]): List[A] = ???
}

// the typeclass
trait Ordering[A] {
  def compare(l: A, r: A): Boolean
}

We provide implicit instances for primitive types like String, and we can also automatically derive instances for types like Tuple2:

object Ordering {
  // typeclass instance for type String
  implicit stringOrdering: Ordering[String] = ???

  // typeclass instance for type Int
  implicit intOrdering: Ordering[Int] = ???

  // typeclass derivation: we can order a Tuple2 if we can order the component types
  implicit def tuple2Ordering[A, B](implicit
      oa: Ordering[A],
      ob: Ordering[B]): Ordering[(A, B)] = {
    case ((la, lb), (ra, rb)) =>
      if (oa.compare(la, ra))
        ...
  }
}


Building bigger tuples

We can use Tuple2 to represent any number of types, by nesting:
type Flat[A, B, C, D]   = (A,  B,  C, D) // really a Tuple4
type Nested[A, B, C, D] = (A, (B, (C, D)))

// we can convert one to the other without losing information
def parenthesize[A, B, C, D](t4: (A, B, C, D)): (A, (B, (C, D)))
Do we use tuples everywhere? NO

We use case class:
case class Foo(s: String, i: Int)

val foos: List[Foo] = ???

// the typeclass instance for type Foo
implicit val fooOrdering: Ordering[Foo] =
  new Ordering[Foo] {
    def compare(l: Foo, r: Foo): Boolean = ???
  }

foos.sorted() // look ma, no arg!
But a case class is "the same" as a tuple! Let's convert between these types:
case class Foo(s: String, i: Int) <-> (String, Int)
case class Bar(s: String, i: Int) <-> (String, Int)
case class Baz(s: String, i: Int, l: Long) <-> (String, Int, Long) <-> (String, (Int, Long))

def toTuple(foo: Foo): (String, Int) = (foo.s, foo.i)
def fromTuple(si: (String, Int)): Foo = Foo(si._1, si._2)
The big idea for deriving typeclass instances for case classes: case class with fields -> tupleN -> nested tuple2 -> implicit deriviation of tuple via implicit components


Q: How do libraries provide these automatic things for most types?

they provide typeclass instances for all primitive types (String, Int, Long)
and also typeclass instances for tuples and List, Option, Either, etc.


Q: How do we automagically convert case classes to whatever tuple typeclass instance thing the library needs?

A: We use shapeless. It uses a macro.


Using shapeless to deconstruct case class into tuples

Shapeless provides the Generic[A] typeclass, whose job is to convert between an A and it's generic representation (type Repr).
Typeclass instances are generated by a macro.
trait Generic[A] {
  type Repr // representation

  def to(a: A): Repr
  def from(repr: Repr): A
}

val genFoo: Generic[Foo] = ??? // uses a macro to generate this
genFoo.Repr = (String, Int) <-- not the real Repr type, sorry

What about nested types?

case class Bar(foo: Foo, l: Long) <-> ((String, Int), Long) <-> (String, (Int, Long))
case class Foo(s: String, i: Int) <-> (String, Int)

We can only handle case classes (product types, AND) and sealed trait hierarchies (enumerations, sum type, OR)

SPOILER: Shapeless doesn't use tuples, it actually uses HList.

First we need to understand type-level lists:
(A,  B,  C,  D)             // Tuple4
(A, (B, (C,  D)))           // nested Tuple2

case object EOL             // End Of List
(A, (B, (C, (D, EOL.type))) // nested Tuple2 with EOL to mark the end of the "list"
This is the class "cons cell" representation of a list. Here's a list of values:
sealed trait MyList[A]
case class MyNil[A]() extends MyList[A]
case class MyPair[A](head: A, tail: MyList[A]) extends MyList[A]

MyPair(12, MyPair(2, MyNil()))
We can do the same thing, but with types:
// Heterogeneous List
sealed trait HList
case object HNil extends HList
case class HPair[H, T <: HList](head: H, tail: T)

type ::[H, T <: HList] = HPair[H, T] // type alias to make the types look prettier

case class Foo(s: String, Int) <-> HPair[String, HPair[Int, HNil]] <-> (String :: Int :: HNil)

val genFoo: Generic[Foo] = ??? // uses a macro to generate this
genFoo.Repr = String :: Int :: HNil
Type-level numbers

type Nat {
  type This
  type Incr = Succ[This]
}

case object Zero extends Nat {
  type This = this.type
}

case class Succ[N <: Nat] extends Nat

type One = Succ[Zero]
type Two = Succ[One]

trait SizedList[A, N <: Nat] {
  def append(a: A): SizedList[A, Succ[N]]
}
References


Type Astronaut's Guide to Shapeless