class: center, middle # Introduction to Algebraic Types in Scala Rob Norris / `@tpolecat` ??? - name is rob - interested in FP - like a challenge so i do it in scala - going to talk about algebraic types - please ask questions. this is a *beginner* talk so if there is anything at all that doesn't make sense, raise your hand or interrupt me --- # Goals - Understand why they're called "algebraic" types. - Understand some elementary isomorphisms. - Understand some common standard library types and operations. - Understand how to write your own. ??? - so I may say ADT, and in the ML/Haskell/Scala world this means "algebraic data type", not to be confused with "abstract data type --- # What do you mean by "algebraic?" ## Let's do some counting. > How many values of type `Nothing`? > > How many values of type `Unit`? > > How many values of type `Boolean`? > > How many values of type `Byte`? > > How many values of type `String`? --- # What do you mean by "algebraic?" ## Let's do some counting. > How many values of type `Nothing`? → 0 > > How many values of type `Unit`? → 1 > > How many values of type `Boolean`? → 2 > > How many values of type `Byte`? → 256 > > How many values of type `String`? → many ??? --- # What do you mean by "algebraic?" ## Let's do some counting. > How many values of type `(Byte, Boolean)`? > > How many values of type `(Byte, Unit)`? > > How many values of type `(Byte, Byte)`? > > How many values of type `(Byte, Boolean, Boolean)`? > > How many values of type `(Boolean, String, Nothing)`? ??? - everyone familiar with tuple types in scala? --- # What do you mean by "algebraic?" ## Let's do some counting. > How many of type `(Byte, Boolean)`? → 2 × 256 = 512 > > How many of type `(Byte, Unit)`? → 256 × 1 = 256 > > How many of type `(Byte, Byte)`? → 256 × 256 = 65536 > > How many of type `(Byte, Boolean, Boolean)`? → 256 × 2 × 2 = 1024 > > How many of type `(Boolean, String, Nothing)`? → 2 × many × 0 = 0 ??? - so to figure out the cardinality of a tuple type like this, you multiply the cardinalities of the component types. - that's why they're called ... --- # What do you mean by "algebraic?" ## Product types! This <u>and</u> That ### Tuples! ```scala type Person = (String, Int) ``` ### Classes! ```scala class ScalaPerson(val name: String, val age: Int) class JavaPerson { final String name; final Int age; ... } ``` ??? - And you have seen these before. - Pretty much every language has product types like tuples or records or structs or classes. - So we all have an instinct about multiplying types. But you can also add them, which will be new for most of you. --- # What do you mean by "algebraic?" ## Let's do some more counting. > How many values of type `Byte` or `Boolean`? > > How many values of type `Boolean` or `Unit`? > > How many values of type `(Byte, Boolean)` or `Boolean`? > > How many values of type `Boolean` or `(String, Nothing)`? ??? - So this is something you may not ever think about if you're coming from a traditional OO language. - What if you have a choice of one thing or another? --- # What do you mean by "algebraic?" ## Let's do some more counting. > How many of type `Byte` or `Boolean`? → 2 + 256 = 258 > > How many of type `Boolean` or `Unit`? → 2 + 1 = 3 > > How many of type `(Byte, Boolean)` or `Boolean`? → (256 × 2) + 2 = 514 > > How many of type `Boolean` or `(String, Nothing)`? → 2 + (many × 0) = 2 ??? - In this case we *add* the cardinalities together, which is why they're called... --- # What do you mean by "algebraic?" ## Sum types! This <u>or</u> That ```scala // What have we learned? Nothing = 0 Unit = 1 Boolean = 2 Byte = 256 (Unit , Boolean) = 1 × 2 = 2 Unit | Boolean = 1 + 2 = 3 // not Scala syntax (Byte , Boolean) = 256 × 2 = 512 Byte | Boolean = 256 + 2 = 258 (Boolean, Boolean, Boolean, Boolean, Boolean, Boolean, Boolean, Boolean) = 256 // sums all the way down Boolean = true | false Int = 1 | 2 | 3 | ... ``` ??? - so we'll get to the exact encoding of this idea in scala, but i wanted to explain this notion of multiplication and addition of types because that's where the "algebraic" comes from. - and we can do much more than add and multiply; function types are actually exponentials, and the derivative of a type is a structure called a one-hole context that's the key to a family of data structures called zippers. We won't talk any more about this but I'll give you a reference if you want to explore that. - Ok so something interested we see is that a tuple of 8 booleans has exactly the same number of inhabitants as byte. so the types are isomorphic, you can line them up 1:1 and convert between them without losing information. - Another interesting thing is that anything times unit is just that thing; unit is the multiplicative identity for types. The takeaway is that there is never any reason to use unit in a product type (or, for related reasons, as a function parameter). - So, understanding when types are equivalent is a nice skill to have. - Alright, moving on. How do we represent sum types in Scala? --- # Sum types in Scala ## Encoded by Subclassing ```scala sealed trait Pet case class Cat(name: String) extends Pet case class Fish(name: String, color: Color) extends Pet case class Squid(name: String, age: Int) extends Pet val bob: Pet = Cat("Bob") ``` - Pro tip: in Scala when you hear ADT it means sum type. ??? - Ok so we have a sealed trait, which means all implementations of that trait must be in the same source file so the compiler knows about all of them. And I'll explain why that's important in a minute. - we don't think of this as a class hierarchy - we think of it as a single type, Pet, with three constructors - so Pet is a sum of three products. - so if bob is a pet, he can be a cat or a fish or a squid, which we inspect... --- # Sum types in Scala ## Destructured by <u>pattern matching</u> ```scala def sayHi(p: Pet): String = p match { case Cat(n) => "Meow " + n + "!" case Fish(n, _) => "Hello fishy " + n + "." case Squid(n, _) => "Hi " + n + "." } scala> sayHi(Cat("Bob")) res0: String = Meow Bob! scala> sayHi(Squid("Steve", 10)) res1: String = Hi Steve. ``` ??? - So we provide a match with a pattern for each constructor, and the arguments we used to construct the value are bound to variables when we do this so they're available on the right-hand side. So that's a different `n` in each case. - The underscore means we don't care about the value. - So what if we leave a case out, like we don't include a clause for `Squid`? --- # Sum types in Scala ## Exhaustiveness Checking ```scala def sayHi(p: Pet): String = p match { case Cat(n) => "Meow " + n + "!" case Fish(n, _) => "Hello fishy " + n + "." } <console>:14: warning: match may not be exhaustive. It would fail on the following input: Squid(_, _) p match { ^ ``` ??? - Well we get a compiler warning. So this is exhaustive matching, which get if you use a sealed trait because the compiler knows that there are exactly three constructors for Pet. - So you don't always need to use pattern matching because there might be methods on the parent trait that do what you want, but you can always fall back on it if you're not sure what to do. - There is another more general way we can encode destructuring, called a fold. We will see this in a minute. - Everyone ok so far? - Ok let's look at some of the ADTs that come in stdlib --- # Standard Library: Option ## Intuition: computations that may fail to return a value ```scala sealed trait Option[+A] case object None extends Option[Nothing] case class Some[A](a: A) extends Option[A] ``` ## Example ```scala def safeDiv(a: Int, b: Int): Option[Int] = if (b != 0) Some(a / b) else None scala> val x = safeDiv(10, 2) x: Option[Int] = Some(5) scala> val y = safeDiv(10, 0) y: Option[Int] = None ``` ??? - do you understand everthing here? type param, covariant, Nothing - puzzle: what's the cardinality of Option? - so this is what we do instead of using null in scala - code: pattern match, fold (cata), map, getOrElse, not talking about flatMap - show dash --- # Standard Library: Either ## Intuition: computations that may return this or that ```scala sealed trait Either[+A, +B] case class Left[A](a: A) extends Either[A, Nothing] case class Right[B](b: B) extends Either[Nothing, B] ``` ### Example ```scala def safeDiv(a: Int, b: Int): Either[String, Int] = if (b != 0) Right(a / b) else Left("Divide by zero!") scala> val x = safeDiv(10, 2) x: Either[String,Int] = Right(5) scala> val x = safeDiv(10, 0) x: Either[String,Int] = Left(Divide by zero!) ``` ??? - you can use this to return this or that; most commonly you see left for errors and right for success. - code: match, not that many methods: fold, swap, projections: map, toOption - puzzle: what's the cardinality of Either? - note that Either[Unit,A] is isomorphic to Option[A] --- # Standard Library: Try ## Intuition: computations that may fail with an exception ```scala sealed trait Try[+A] case class Success[A](a: A) extends Try[A] case class Failure[A](t: Throwable) extends Try[A] ``` ### Example ```scala import util._ // it's scala.util.Try def safeDiv(a: Int, b: Int): Try[Int] = Try(a / b) scala> val x = safeDiv(10, 2) x: scala.util.Try[Int] = Success(5) scala> val x = safeDiv(10, 0) x: scala.util.Try[Int] = Failure(java.lang.ArithmeticException: / by zero) ``` ??? - isomorphic with Either[Throwable,A] - code: no fold, match, map, map w/ error "bulletproof principle" --- # Standard Library: List ## Intuition: computations that may return many answers ```scala sealed trait List[+A] case object Nil extends List[Nothing] case class ::[A](head: A, tail: List[A]) extends List[A] object List { def apply[A](as: A*): List[A] = ... } ``` ### Example ```scala def sum(ns: List[Int]): Int = ns match { case Nil => 0 case n :: ns => n + sum(ns) } scala> sum(List(1,2,3)) res23: Int = 6 ``` ??? - a bit more here. we have an empty case and a non-empty case like option - and there's some syntax that helps us not have to deal with `::` directly. - list is an inductive type because it has a base case Nil, and an inductive case cons that takes a smaller list as an argument. And functions over lists have the same form as an inductive proof. - code: foldRight, map, flatMap, headOption --- class: center, middle # Thanks! Questions? Rob Norris / `@tpolecat` <small>Code will be available soon, watch the tweeter.</small> ??? - feedback, complaints