Typeclasses -- a type system construct

Typeclasses are widely in use on advanced Scala code and yet they are not a first class citizen of the language. This talk will introduce the concept of typeclasses from the ground up by looking at languages such as Haskell and Rust.

Typeclass coherence (multiple instances of the same typeclass for the same type), effective namespacing and implicit resolution (in Scala) are some of the challenges that arise for extensive usage of this concept and language feature. We'll explore those issues and how other languages deal with them.

The focus will then shift on how to apply the learnings from other languages to improve the readability and usability of typeclasses in Scala via conventions and reliance on tools such as macro annotations. The _Cats_ and _Simulacrum_ libraries, among others, will serve as case studies and examples.

Transcript

2. TYPECLASSES a type system construct ANDREA LATTUADA — @utaal 2
3. 1. why typeclasses 2. as first-class citizens, encoded 3. complications arising from encoding 4. case studies, good practices 3
4. TYPECLASSES ATTACH FUNCTIONS TO EXISTING DATA-TYPES SUPPORT ad-hoc POLYMORPHISM 4
5. case class Square(side: Float) case class Rectangle(a: Float, b: Float) case class Circle(radius: Float) def area(square: Square): Float = Math.pow(square.side, 2).toFloat def area(rectangle: Rectangle): Float = rectangle.a * rectangle.b def area(circle: Circle): Float = (Math.PI * Math.pow(circle.radius, 2)).toFloat def compareArea( a: A forSome { type A for which there's a function area(A):Float }, b: B forSome { type B for which there's a function area(B):Float } ): Float = area(a) - area(b) compareArea(Square(10), Circle(5)) 5
6. GROUP TYPES THAT support certain operations, WITH SUBTYPING trait HasArea { def area: Float } case class Square(side: Float) extends HasArea { def area = Math.pow(square.side, 2).toFloat } case class Rectangle(a: Float, b: Float) extends HasArea { def area = this.a * this.b } def compareArea( a: A forSome { type A <: HasArea }, b: B forSome { type B <: HasArea }): Float = a.area - b.area 6
7. GROUP TYPES FOR WHICH certain operations are supported, WITH TYPECLASSES Square, Rectangle, Circle support def area(x): Float def area(square: Square): Float = ... def area(rectangle: Rectangle): Float = ... def area(circle: Circle): Float = ... defined ad-hoc 7
8. typeclass HasArea[T] { def area(t: T): Float } def compareArea[A, B]( a: A forSome { type A in typeclass HasArea }, b: B forSome { type B in typeclass HasArea } ): Float = area(a) < area(b) Type variables A and B can only be instantiated to a type whose members support the operations associated with typeclass HasArea.1 1 https://en.wikipedia.org/wiki/Type_class 8
9. DEFINE SUPPORTED OPERATIONS FOR A TYPECLASS -- Haskell class HasArea a where area :: a -> Float // Scala typeclass HasArea[T] { def area(t: T): Float } 9
10. PROVIDING AN IMPLEMENTATION FOR A TYPE MAKES IT A member OF THE TYPECLASS. data Square = Square { side :: Float } deriving Show data Rectangle = Rectangle { a :: Float, b :: Float } deriving Show data Circle = Circle { radius :: Float } deriving Show class HasArea a where area :: a -> Float instance HasArea Square where area x = side x ^^ 2 instance HasArea Rectangle where area x = a x * b x instance HasArea Circle where area x = pi * radius x ^^ 2 10
11. WE CAN restrict A TYPE VARIABLE TO TYPES BELONGING TO A CERTAIN TYPECLASS -- Haskell class HasArea a where area :: a -> Float ... compareArea :: HasArea a => HasArea b => a -> b -> Float // Scala def compareArea( a: A forSome { type A for which there is HasArea[A] }, b: B forSome { type B for which there is HasArea[B] }): Float 11
12. data Square = Square { side :: Float } deriving Show data Rectangle = Rectangle { a :: Float, b :: Float } deriving Show data Circle = Circle { radius :: Float } deriving Show class HasArea a where area :: a -> Float instance HasArea Square where area x = side x ^^ 2 instance HasArea Rectangle where area x = a x * b x instance HasArea Circle where area x = pi * radius x ^^ 2 compareArea :: HasArea a => HasArea b => a -> b -> Float compareArea a b = area a - area b *Main> compareArea Circle { radius = 3 } Rectangle { a = 2, b = 3 } 22.274334 12
13. TYPECLASS encoding IN SCALA 13
14. IMPLICITS class Something[A] implicit val implicitSomething: Something[Int] = new Something[Int]() // from standard library def implicitly[T](implicit e: T): T scala> implicitly[Something[Int]] res1: Something[Int] = Something@5680a178 14
15. TYPECLASS definition IN SCALA class HasArea a where area :: a -> Float ‑ trait HasArea[A] { def area(x: A): Float } 15
16. TYPECLASS instance IN SCALA data Square = Square { side :: Float } deriving Show instance HasArea Square where area x = side x ^^ 2 ‑ case class Square(side: Float) implicit val squareHasArea: HasArea[Square] = new HasArea[Square] { def area(x: Square): Float = Math.pow(x.side, 2).toFloat } 16
17. TYPECLASS constraint IN SCALA compareArea :: HasArea a => HasArea b => a -> b -> Float compareArea a b = area a - area b ‑ def compareArea[A, B](a: A, b: B) (implicit aHasArea: HasArea[A], bHasArea: HasArea[B]): Float = aHasArea.area(a) - bHasArea.area(b) // or, equivalently (desugars to equivalent form) def compareArea[A: HasArea, B: HasArea](a: A, b: B): Float = implicitly[HasArea[A]].area(a) - implicitly[HasArea[B]].area(b) 17
18. TYPECLASS syntax IN SCALA area $ Square { side = 3.5 } ‑ implicit class areaOps[A: HasArea](a: A) { def area: Float = implicitly[HasArea[A]].area(a) } Square(side = 3.5).area 18
19. TYPECLASS inheritance IN HASKELL class TC a where operation1 :: a -> a -> Bool class TC a => SubTC a where operation2 :: a -> a -> Int SubTC inherits TC's operations every instance of SubTC for a type T is also an instance of TC for T use_ops :: (SubTC a) => a -> a -> a -> Bool use_ops a b c = (operation1 a b) && (operation1 b c) 19
20. ENCODING TYPECLASS inheritance IN SCALA trait TypeClass[T] { def operation1(a: T, b: T): Boolean } trait SubTypeClass[T] extends TypeClass[T] { def operation2(a: T, b: T): Int } ꔇ def use_ops[T](a: T, b: T, c: T)( implicit instance: SubTypeClass[T]): Boolean = instance.operation1(a, b) && instance.operation1(b, c) 20
21. {HASKELL, RUST} ➡ SCALA 21
22. TYPECLASS instance scope (WHERE THE COMPILER SEARCHES FOR INSTANCES) 22
23. ORPHAN INSTANCES An orphan instance is a type class instance for class C and type T which is neither defined in the module where C is defined nor in the module where T is defined.2 2 https://wiki.haskell.org/Orphan_instance 23
24. HASKELL ▸ open world assumption ▸ instances imported when importing a module that defines them or imports them (no hiding possible) — even when the typeclass is not in scope 24
25. RUST ▸ instances can only be defined in the same file as the datatype or the typeclass (no orphan instances) ▸ instances available when the trait is imported 25
26. SCALA based on implicit resolution ▸ most specific first ▸ search in implicit scope and companion objects 26
27. SCALA: MOST SPECIFIC FIRST trait SomeTypeclass[T] { val where: String } // wildcard instance implicit def genericSomeTypeclass[T]: SomeTypeclass[T] = new SomeTypeclass[T] { val where = "generic" } implicit val someTypeclassString: SomeTypeclass[String] = new SomeTypeclass[String] { val where = "specific" } > implicitly[SomeTypeclass[String]].where res1: String = "specific" 27
28. SCALA: DIFFERENT ORIGIN 1. (implicit scope) local scope, imported or inherited values/defs if one in both available, ambiguous implicit ▸ among imported or inherited values/defs, the one defined in the most specific type 2. companion object of the datatype or typeclass 28
29. SCALA: ISSUES ▸ (readability) where is this instance coming from? ▸ (discoverability) where do I find available instances for a certain typeclass? ▸ (coherence, maintainability) what instance am I using when multiple are available? 29
30. SCALA: COHERENCE AND MAINTANABILITY object HasArea { implicit val rectangleHasArea = new HasArea[Rectangle] { def area(r: Rectangle): Double = r.a * r.b } } ꔇ class Module { implicit sphericalRectangleHasArea = new HasArea[Rectangle] { def area(r: Rectangle): Double = f(r.a, r.b) } compareArea(Rectangle(10, 12), Rectangle(13, 14)) } 30
31. COHERENCE: BLANKET IMPLEMENTATIONS trait RootJsonCodec[T] trait DbCodec[T] implicit def dbCodecRootJsonCodec[A]( implicit c: RootJsonCodec[T]): DbCodec[T] 31
32. COHERENCE: overlapping BLANKET IMPLEMENTATIONS trait RootJsonCodec[T] trait BinaryCodec[T] trait DbCodec[T] implicit def dbCodecRootJsonCodec[A]( implicit c: RootJsonCodec[T]): DbCodec[T] implicit def dbCodecBinaryCodec[A]( implicit c: BinaryCodec[T]): DbCodec[T] case class Square(side: Double) implicit val squareRootJsonCodec = new RootJsonCodec[Square] {...} implicit val squareBinaryCodec = new BinaryCodec[Square] {...} 32
33. {HASKELL, RUST} ➡ SCALA ▸ define instances in companion objects ▸ define blanket instances in companion objects of target typeclass ▸ be conservative and follow a convention for orphan and blanket instances (more on this later) 33
34. OPERATIONS (SYNTAX) in Haskell and Rust, functions defined/imported along with the typeclass definition 34
35. IN SCALA, OPERATIONS encoded AS AN IMPLICIT CONVERSION implicit class hasAreaOps[A](a: A)( implicit hasArea: HasArea[A]) { def area: Float = implicitly[HasArea[A]].area(a) } 35
36. SIMULACRUM3 addCompilerPlugin("org.scalamacros" % "paradise" % "2.1.0" cross CrossVersion.full) ꔇ import simulacrum._ @typeclass trait HasArea[A] { def area(self: A) } 3 https://github.com/typelevel/cats 36
37. Encoding IN SIMULACRUM @typeclass trait HasArea[A] { def area(self: A): Double } ‑ trait HasArea[A] { def area(self: A): Double } ꔇ 37
38. Syntax IN SIMULACRUM @typeclass trait HasArea[A] { ... } ‑ ꔇ object HasArea { def apply[A](implicit instance: HasArea[A]): HasArea[A] = instance trait Ops[A] { def typeClassInstance: HasArea[A] // for use in impl def self: A // for use in impl def area: Double } ꔇ 38
39. Syntax IN SIMULACRUM, SELECTIVE IMPORT @typeclass trait HasArea[A] { ... } ‑ ꔇ trait ToHasAreaOps { implicit def toHasAreaOps[A](target: A)( implicit tc: HasArea[A]): Ops[A] = new Ops[A] { <impl> } } ꔇ 39
40. Syntax IN SIMULACRUM, ALL OPERATIONS @typeclass trait HasArea[A] { ... } ‑ ꔇ // The AllOps trait mixes in Ops // along with the AllOps traits of all super types. trait AllOps[A] extends Ops[A] { def typeClassInstance: HasArea[A] } object ops { implicit def toAllHasAreaOps[A](target: A)( // implicit conversion implicit tc: HasArea[A]): AllOps[A] = new AllOps[A] { <impl> } } } 40
41. Syntax WITHOUT SIMULACRUM trait HasArea[A] { def area(self: A): Double } object HasArea { object ops { implicit class toHasAreaOps(target: A)( implicit instance: HasArea[A]) { def area: Double = instance.area(target) } } } 41
42. SIMULACRUM does not overwrite THE TYPECLASS' COMPANION OBJECT import simulacrum._ @typeclass trait HasArea[A] { def area(self: A): Double } case class Rectangle(a: Double, b: Double) object HasArea { implicit val rectangleHasArea = new HasArea[Rectangle] { def area(self: Rectangle): Double = self.a * self.b } } 42
43. WHY SIMULACRUM? ▸ robust, consistent object-oriented forwarders ("syntax") ▸ searchable, consistent syntax (@typeclass) 43
44. CATS3 Lightweight, modular, and extensible library for functional programming. 3 https://github.com/typelevel/cats 44
45. CATS: SCOPE AND COHERENCE for cats datatypes, instances defined only in companion objects for scala datatypes, orphan instances defined only in package cats.instances selective import via traits 45
46. CATS INSTANCES: selective IMPORT VIA TRAIT MIXIN import cats.instances.all._ or import cats.instances.list._ or trait FutureInstances { ... } trait OptionInstances { ... } ‑ object MyInstances extends FutureInstances with OptionInstances 46
47. {RUST, CATS} ➡ SCALA ▸ prefer companion objects for typeclasses/datatypes you control ▸ group all orphan instances in a package, allow selective import ▸ avoid overlapping instances, unless there's a specific usability need 47
48. NEWTYPE: SAFER ALTERNATIVE TO OVERLAPPING INSTANCES object HasArea { implicit val rectangleHasArea = new HasArea[Rectangle] { ... } } ꔇ class Module { case class Spherical[A](shape: A) implicit sphericalRectangleHasArea = new HasArea[Rectangle] { def area(r: Rectangle): Double = f(r.a, r.b) } compareArea(Spherical(Rectangle(10, 12)), Spherical(Rectangle(13, 14))) } 48
49. CATS: SYNTAX (OBJECT-ORIENTED FORWARDERS) Cats uses Simulacrum import cats.Monad.ops._ traits for selective import defined in cats.syntax 49
50. {HASKELL, RUST, SIMULACRUM, CATS} ➡ SCALA ▸ (discoverability) syntax defined in the companion object, and re- exported via syntax.all and traits for usability 50
51. ▸ discoverability ▸ readability ▸ coherence/maintainability 51