CSE 130

Generics (Subtyping + Parametric Polymorphism)

Ranjit Jhala, UC San Diego

Announcements

Course Evaluations

CAPE

Topics

Final Exam

Practice Questions

Review Session

A Tale of Two Polymorphisms

Today's Plan

Parametric Polymorphism ("Type Variables"; ML style)

Combining Subtyping + Parametric Polymorphism

Proxies and Implicits

Functions with Type Variables

Parametrically Polymorphic Functions

Unlike OCaml, you have to write down the type variables:

/* val id : 'a -> 'a
/* OCaml: let id x = x */

scala> def id[A](x:A) = x
id: [A](x: A)A

/* val swap : ('a, 'b) -> ('b, 'a) */
/* OCaml: let swap (x, y) = (y, x) */
scala> def swap[A,B](p: (A,B)) = (p._2, p._1)
swap: [A, B](p: (A, B))(B, A)

Parametrically Polymorphic Functions

At function call, can explicitly instantiate the type parameters:

scala> swap[Int, Boolean](1, true)
res10: (Boolean, Int) = (true,1)

But often, local type inference can implicitly instantiate them:

scala> swap(1, true)
res11: (Boolean, Int) = (true,1)

Parametrically Polymorphic Lists

Recall the type ascription expression from last time.

scala> List()
res17: List[Nothing] = List()

scala> List(): List[Int]
res18: List[Int] = List()

scala> List(): List[Boolean]
res19: List[Boolean] = List()

scala> List(): List[List[Int]]
res20: List[List[Int]] = List()

Parametrically Polymorphic Lists

Recall the type ascription expression from last time.

scala> Nil
res23: scala.collection.immutable.Nil.type = List()

scala> Nil: List[Int]
res24: List[Int] = List()

scala> Nil: List[Boolean]
res25: List[Boolean] = List()

scala> Nil: List[List[Int]]
res26: List[List[Int]] = List()

Parametrically Polymorphic Lists

Wait, there are two ways to describe the empty list?

scala> Nil: List[Int]
res24: List[Int] = List()

scala> List(): List[Int]
res18: List[Int] = List()

scala> Nil == List()
res32: Boolean = true

Remember OCaml Datatypes?

Remember OCaml Datatypes?

Datatypes in OCaml were awesome.

# type t = A | B ;;
# let foo x = match x with A -> () ;;     
Warning: this pattern-matching is not exhaustive.
foo : t -> unit

# let bar x = match x with A -> () | B -> () | B -> () ;;
Warning: this match case is unused.
bar : t -> unit

Datatypes vs. Classes

OCaml Datatypes

# type t = A | B ;;

Scala Classes

class t
class A() extends t
class B() extends t

Case Classes

A mix of classes and datatypes...

class t
case class A() extends t
case class B() extends t

... that enables pattern matching!

def foo(x: t) = x match {
  case A() => println("A")
  case B() => println("B")
}

CLICKER: Case Classes

class t
case class A() extends t

def bar(x: t) = x match {
  case A() => println("A")
  case A() => println("A")
}

What is the result of evaluating bar?

A: Type Error

B: t -> Unit

C: t -> Unit with a warning

Case Classes

class t
case class A() extends t

def bar(x: t) = x match {
  case A() => println("A")
  case A() => println("A")
}

CLICKER: Case Classes

class t
case class A() extends t
case class B() extends t

def baz(x: t) = x match {
  case A() => println("A")
}

What is the result of evaluating bar?

A: Type Error

B: t -> Unit

C: t -> Unit with a warning

Case Classes

class t
case class A() extends t
case class B() extends t

def baz(x: t) = x match {
  case A() => println("A")
}

Sealed Classes

If a (regular or case) class is marked as sealed...

sealed class t
case class A() extends t
case class B() extends t
def baz(x: t) = x match {
  case A() => println("A")
}

Parametric Polymorphism: List Length

(* ML *)
let rec length xs = match xs with
  | []   -> 0
  | _::t -> 1 + length t
/* Scala */
def length[A](xs: List[A]): Int =
  xs match {
    case Nil      => 0
    case (_ :: t) => 1 + length(t)
  }

Parametric Polymorphism: List Map

(* ML *)
let rec map f xs = match xs with
  | []   -> []
  | x::t -> (f x) :: map (f, t)
/* Scala */
def map[A, B](f: A => B)(xs: List[A]): List[B] =
  xs match {
    case Nil      => List()
    case (_ :: t) => (f(x))::(map(f)(t))
  }

Are These Functions Equivalent?

// Subtype Polymorphism
def headAny(xs: List[Any]): Any =
  xs match {
    case h :: _ => h
    case _      => sys.error("head of empty list")
  }

// Parametric Polymorphism
def headPoly[A](xs: List[A]): A =
  xs match {
    case h :: _ => h
    case _      => sys.error("head of empty list")
  }

Are These Functions Equivalent?

// Subtype Polymorphism
def headAny(xs: List[Any]): Any = ...

// Parametric Polymorphism
def headPoly[A](xs: List[A]): A = ...

Are These Functions Equivalent?

// Subtype Polymorphism
def headAny(xs: List[Any]): Any = ...

// Parametric Polymorphism
def headPoly[A](xs: List[A]): A = ...

scala> val ns = List(1,2,3)
ns: List[Int] = List(1, 2, 3)

scala> val (i, j) = (headAny(ns), headPoly(ns))
i: Any = 1
j: Int = 1

Classes/Traits with Type Variables

Parametrically Polymorphic Classes

Parametrically Polymorphic Classes

sealed abstract class Bag[A]
case class Empty[A]() extends Bag[A]
case class Plus[A](elt: A, rest: Bag[A]) extends Bag[A]
type 'a bag = Empty | Plus of ('a * 'a bag)

Parametrically Polymorphic Classes

sealed abstract class Bag[A]
case class Empty[A]()                    extends Bag[A]
case class Plus[A](elt: A, rest: Bag[A]) extends Bag[A]

Case Classes are Just Vanilla Classes...

Parametrically Polymorphic Classes

sealed abstract class Bag[A]
case class Empty[A]()                    extends Bag[A]
case class Plus[A](elt: A, rest: Bag[A]) extends Bag[A]

Parametrically Polymorphic Classes

We can fill in various methods...

sealed abstract class Bag[A] {
  ...
  def size : Int =
    this match {
      case Empty()       => 0
      case Plus(_, rest) => 1 + rest.size
    }
  ...
}

Parametrically Polymorphic Classes

We can fill in various methods...

sealed abstract class Bag[A] {
  // ...
  def contains(x: A) : Boolean = {
    this match {
      case Empty()                => false
      case Plus(e, _) if (x == e) => true  
      case Plus(_, rest)          => rest.contains(x)
    }
  }
  // ...
}

Parametrically Polymorphic Classes

We can fill in various methods...

sealed abstract class Bag[A] {
  // ...
  def add(x: A) : Bag[A] = {
    if (this.contains(x)) this else { Plus(x, this) }
  }
  // ...
}

Parametrically Polymorphic Classes

We can fill in various methods...

sealed abstract class Bag[A] {
  // ...
  def gimme: Option[A] =
    this match {
      case Plus(x, rest) => Some(x)
      case _             => None
    }
  // ...
}

Today's Plan

Parametric Polymorphism ("Type Variables"; ML style)

Combining Subtyping + Parametric Polymorphism

Proxies and Implicits

Combining Subtyping
+ Parametric Polymorphism

CLICKER: What is the value of res?

def findMin[A](cur: A, xs: List[A]): A = xs match {
    case Nil               => cur
    case h::t if (h < cur) => findMin(h, t)
    case _::t              => findMin(cur, t)
}

val res = findMin(1000, List(20, 4, 1, 6))

A. Type Error in findMin(1000, ...)

B. Type Error in definition of findMin

C. Type Error in List(20,4,1,6)

D. 1

E. 20

What is the value of res?

def findMin[A <: Ord[A]](cur: A, xs: List[A]): A = xs match {
    case Nil               => cur
    case h::t if (h < cur) => findMin(h, t)
    case _::t              => findMin(cur, t)
}

val res = findMin(1000, List(20, 4, 1, 6))
error: value < is not a member of type parameter A
           case h::t if (h < cur) => findMin(h, t)
                           ^

Want to describe WHICH types
support comparison...

Traits!

trait Ord[A] {
  def cmp(that: A): Int // Must Be Implemented ...

  // ... Automatically derived from cmp !
  def ===(that: A): Boolean = (this cmp that) == 0
  def <(that: A): Boolean   = (this cmp that) < 0
  def >(that: A): Boolean   = (this cmp that) > 0
  def <=(that: A): Boolean  = (this cmp that) <= 0
  def >=(that: A): Boolean  = (this cmp that) <= 0
}

Ord.scala

An Ordered List...

def findMin[???](cur: ???, xs: List[???]): ??? =
  xs match {
    case Nil               => cur
    case h::t if (h < cur) => findMin(h, t)
    case _::t              => findMin(cur, t)
  }

An Ordered List... with Bounded Quantification

def findMin[A <: Ord[A]](cur: A, xs: List[A]): A =
  xs match {
    case Nil               => cur
    case h::t if (h < cur) => findMin(h, t)
    case _::t              => findMin(cur, t)
  }

Bag is a pretty lame data structure

An Ordered Bag

sealed abstract class Bag[A <: Ord[A]] {
  // ...
}

An Ordered Bag

A faster version of contains that does not walk the entire bag.

sealed abstract class Bag[A <: Ord[A]] {
  // ...
  def contains(x: A) : Boolean =
    this match {
      case Empty()                => false
      case Plus(e, _) if (x == e) => true  
      case Plus(e, _) if (x  > e) => false
      case Plus(_, rest)          => rest.contains(x)
  }
  // ...
}

An Ordered Bag

... Assuming that elements are ordered in the first place!

So, we must change the add method to enforce this invariant.

sealed abstract class Bag[A <: Ord[A]] {
  // ...
  def add(x: A) : Bag[A] =
    this match {
      case Plus(e, es) if (x > e)  => Plus(e, es.add(x))
      case Plus(e, _)  if (x == e) => this
      case _                       => Plus(x, this)
    }
  // ...
}

An Ordered Bag

The remove method can also be made a bit more efficient.

No need to go to the end:

sealed abstract class Bag[A <: Ord[A]] {
  // ...
  def remove(x: A) : Bag[A] =
   this match {
    case Plus(e, es) if (x <  e) => this
    case Empty()                 => this
    case Plus(e, es) if (x == e) => es
    case Plus(e, es)             => Plus(e, es.remove(x))
  }
  // ...
}

RECAP: Bounded Quantification

[A <: T] describes

CLICKER: What is the value of res?

def findMin(cur: A, xs: List[A]): A =
  xs match {
    case Nil               => cur
    case h::t if (h < cur) => findMin(h, t)
    case _::t              => findMin(cur, t)
  }

val res = findMin(1000, List(20, 4, 1, 6))

A. Type Error in findMin(1000, ...)

B. Type Error in definition of findMin

C. 1

What is the value of res?

def findMin[A <: Ord[A]](cur: A, xs: List[A]): A =
  xs match {
    case Nil               => cur
    case h::t if (h < cur) => findMin(h, t)
    case _::t              => findMin(cur, t)
  }

val res = findMin(1000, List(20, 4, 1, 6))

What is the value of res?

scala> val res = findMin(1000, List(1,2,3))
error: inferred type arguments [Int] do not conform to
       method findMin's type parameter bounds
       [A <: Ord[A]]
scala> val res = findMin[Int](1000, List(1,2,3))
error: type arguments [Int] do not conform to
       method findMin's type parameter bounds
       [A <: Ord[A]]

How to Add Functionality to Existing Types?

Today's Plan

Parametric Polymorphism ("Type Variables"; ML style)

Combining Subtyping + Parametric Polymorphism

Proxies and Implicits

Retrofitting Functionality with Proxies




trait Wierd {
  def godZilla : Int
}

def foo(x : Wierd) = println("Sooo wierd")

def findMin[A](cur: A, xs: List[A])(implicit sideKick: A => Ord[A]): A =
  xs match {
    case Nil               => cur
    case h::t if (h < cur) => findMin(h, t)
    case _::t              => findMin(cur, t)
  }

implicit def intSideKick(x:Int) = new Ord[Int] {
  def cmp(that : Int) = x - that
  }

implicit def strSideKick(x:String) = new Ord[String] {
  def cmp(that : String) = x compare that
  }


Will it work?

A. Yes
B. No

Retrofitting Functionality with Proxies

def findMin[A](cur: A, xs: List[A])(proxy: A => Ord[A]) =
  xs match {
    case Nil                      => cur
    case h::t if (proxy(h) < cur) => findMin(h, t)
    case _::t                     => findMin(cur, t)
  }

def intProxy(x: Int) = new Ord[Int] {
  def cmp(that: Int) : Int = x - that
}

Retrofitting Functionality with Proxies

def findMin[A](cur: A, xs: List[A])(proxy: A => Ord[A]) =
  xs match {
    case Nil                      => cur
    case h::t if (proxy(h) < cur) => findMin(h, t)(proxy)
    case _::t                     => findMin(cur, t)(proxy)
  }

def intProxy(x: Int) = new Ord[Int] {
  def cmp(that: Int) : Int = x - that
}

scala> import ProxyDemo._
scala> findMin(1000, List(20, 4, 1, 6))(intProxy)
res1: Int = 1

Retrofitting Functionality with Proxies

Of course, we can create proxies for other types, too:

def stringProxy(x: String) = new Ord[String] {
  def cmp(that: String) : Int = x compare that
}

scala> import ProxyDemo._
scala> findMin("zz", List("apple", "chorizo", "adobado"))
              (stringProxy)
res1: String = "adobado"

Retrofitting Functionality with Proxies

Proxies are Awesome

... But Proxies are Also Lame

Let's Keep the Awesome and
Eliminate the Lame

Implicit Parameters and Values

// Mark certain function params as implicit
def sayHello(implicit n: String) = println("Hello " + n)

// Mark certain values as implicit
implicit val defaultName = "Ranjit"
scala> sayHello("Roberto")
Hello Roberto

Implicit Parameters and Values

// Mark certain function params as implicit
def sayHello(implicit n: String) = println("Hello " + n)

// Mark certain values as implicit
implicit val defaultName = "Ranjit"
scala> sayHello("Roberto")
Hello Roberto
scala> sayHello
Hello Ranjit

Implicits: The Magic of Types

Scala uses types to fill in the blanks.

Implicits: Automatically "Fix" Type Errors

Suppose I wrote a function expecting String inputs

scala> def yu(msg: String) = println("Y U  NO " + msg)
yu: (msg: String)Unit

Naturally, this is fine ...

scala> yu("GIVE EASY FINAL")
Y U  NO GIVE EASY FINAL

... but this throws an error

scala> yu(10)
<console>:9: error: type mismatch;
 found   : Int(10)
 required: String
       yu(10)
          ^

Implicits: Automatically "Fix" Type Errors

Suppose I wrote a function expecting String inputs

scala> def yu(msg: String) = println("Y U  NO " + msg)
yu: (msg: String)Unit

But if we add an implicit conversion

scala> implicit def i2s(i: Int) = i.toString
i2s: (i: Int)java.lang.String

Then lo and behold!

scala> yu(10)       
Y U  NO 10

Retrofitting Functionality

Retrofitting Functionality with Implicit Proxies

Step 1: Make proxy parameters implicit

def findMin[A](cur: A, xs: List[A])
              (implicit proxy: A => Ord[A]): A =
 xs match {
   case Nil                      => cur
   case h::t if (proxy(h) < cur) => findMin(h, t)(proxy)
   case _::t                     => findMin(cur, t)(proxy)
 }

Retrofitting Functionality with Implicit Proxies

Step 2: Remove explicit uses of proxy

(Scala automatically inserts them!)

def findMin[A](cur: A, xs: List[A])
              (implicit proxy: A => Ord[A]): A =
 xs match {
   case Nil                        => cur
   case h::t if (/*proxy*/h < cur) => findMin(h, t)
   case _::t                       => findMin(cur, t)
 }

Retrofitting Functionality with Implicit Proxies

Step 3: Make proxy functions implicit

implicit def intProxy(x: Int) = new Ord[Int] {
  def cmp(that: Int) : Int = x - that
}

implicit def stringProxy(x: String) = new Ord[String] {
  def cmp(that: String) : Int = x compare that
}

Retrofitting Functionality with Implicit Proxies

  1. Make proxy parameters implicit.

  2. Remove explicit uses of proxy. (Scala automatically inserts them!)

  3. Make proxy functions implicit.

scala> val res = // look ma, no proxies!
         findMin(1000, List(10, 2, 30, 14))
res: Int = 2

Retrofitting Functionality with Implicit Proxies

This pattern is so common that it warrants special syntax.

Instead of:

def findMin[A](cur: A, xs: List[A])
              (implicit proxy: A => Ord[A]): A

We can just write the equivalent:

def findMin[A <% Ord[A]](cur: A, xs: List[A]): A

Retrofitting Functionality with Implicit Proxies

We can now make a real ordered bag

sealed abstract class Bag[A <% Ord[A]] {

  def contains(x: A) : Boolean = {
    this match {
      case Empty()                => false
      case Plus(e, _) if (x == e) => true  
      case Plus(e, _) if (x  > e) => false
      case Plus(_, rest)          => rest.contains(x)
    }
  }

  // etc.

Today's Plan: A Tale of Two Polymorphisms

  1. Parametric Polymorphism ("type variables", ML style)

    • def add[A](x: A): Bag[A]
  2. Subtyping + Parametric Polymorphism

    • def add[A <: Ord[A]](x: A): Bag[A]
  3. Implicitly retrofitting behavior to existing types

    • def add[A <% Ord[A]](x: A): Bag[A]

See the code

Typeclass Pattern

Why not Implicit Proxies?

Why not Implicit Proxies?

trait Cool130App {
  implicit def intProxy(x: Int) = new Ord[Int] {
    def cmp(that: Int) : Int = x - that
  }
}

object Test extends Cool130App {
  val tb = Bag(2,3,4)
}

Typeclasses to the rescue

Typeclasses to the rescue

case class Cow(name: String)
case class Dog(name: String)
case class Kitty(name: String)

Typeclasses to the rescue

Typeclasses to the rescue

trait Says[A] {
  def talk(thing: A): String
}

Typeclasses to the rescue

trait Says[A] {
  def talk(thing: A): String
}
object CowSays extends Says[Cow] {
  def talk(thing: Cow) = thing.name + " say mooooo"
}

scala> val cow = Cow("jerry")
cow: Cow = Cow(jerry)

scala> CowSays.talk(cow)
res1: String = jerry say mooooo

Typeclasses to the rescue

Typeclasses to the rescue

object CowSays extends Says[Cow] {
  def talk(thing: Cow) = thing.name + " say mooooo"
}
object KittySays extends Says[Kitty] {
  def talk(thing: Kitty) = thing.name + " say meooww"
}

scala> val (cow, kitty) = (Cow("jerry"), Kitty("ranjit"))
cow: Cow = Cow(jerry)
kitty: Kitty = Kitty(ranjit)

scala> CowSays.talk(cow)
res1: String = jerry say mooooo

scala> KittySays.talk(kitty)
res1: String = ranjit say meooww

Typeclasses to the rescue

scala> Animal.talk(cow)
res1: String = jerry say mooooo

scala> Animal.talk(kitty)
res1: String = ranjit say meooww

Typeclasses to the rescue

implicit object CowSays extends Says[Cow] {
  def talk(thing: Cow) = thing.name + " say mooooo"
}

implicit object KittySays extends Says[Kitty] {
  def talk(thing: Kitty) = thing.name + " say meooww"
}

object Animal {
  def talk[A](animal: A)(implicit says: Says[A]) =
    says.talk(animal)
}

Typeclasses to the rescue

implicit object CowSays   extends Says[Cow] ...
implicit object KittySays extends Says[Kitty] ...

object Animal {
  def talk[A](animal: A)(implicit says: Says[A]) =
    says.talk(animal)
}
scala> Animal.talk(cow)
res0: String = jerry say mooooo

Typeclasses with Tuples!

Typeclasses with Tuples!

implicit def saysTuple[A, B]
    (implicit saysA: Says[A], saysB: Says[B])
  = new Says[(A, B)] {
    def talk(thing: (A, B)) =
      saysA.talk(thing._1) + " and " + saysB.talk(thing._2)
}

Typeclasses with Tuples!

Typeclasses with Tuples!

scala> Animal.talk((cow, kitty))
res0: String = jerry say mooooo and ranjit say meooww

Typeclasses with Tuples, Pretty Version

Typeclasses with Tuples, Pretty Version

implicit def saysTuple[A, B]
    (implicit saysA: Says[A], saysB: Says[B])
  = new Says[(A, B)] {
    def talk(thing: (A, B)) =
      saysA.talk(thing._1) + " and " + saysB.talk(thing._2)
}

Typeclasses with Tuples, Pretty Version

implicit def saysTuple[A, B]
    (implicit saysA: Says[A], saysB: Says[B])
  = new Says[(A, B)] {
    def talk(thing: (A, B)) =
      saysA.talk(thing._1) + " and " + saysB.talk(thing._2)
}
implicit def saysTuple[A : Says, B : Says]
  = new Says[(A, B)] {
    def talk(thing: (A, B)) =
      Animal.talk(thing._1) + " and " + Animal.talk(thing._2)
}

Typeclasses with Lists, Pretty Version

Or for lists

implicit def saysTuple[A : Says]
  = new Says[List[A]] {
    def talk(things: List[A]) =
      things.map(Animal.talk(_)).mkString(", ")
    }

Typeclasses

COURSE WRAP-UP

Course Wrap-Up

We have studied many general themes in the context of

Theme: Expressions, Values, Types

Expressions and Values

Theme: Expressions, Values, Types

Types

Theme: First-Class Functions

Theme: Immutable vs. Mutable Data

Theme: Type Inference

Course Wrap-Up

Remember these powerful building blocks when you:

</CSE 130>

Digression

Digression: Cons

How does cons work?

scala> 1 :: 2 :: 3 :: Nil
res27: List[Int] = List(1, 2, 3)

Fixity of Operators

Methods that end in : (like cons ) are associated from right-to-left.

scala> 1.::(2.::(3.::(Nil)))
res33: List[Double] = List(1.0, 2.0, 3.0)

scala> Nil.::(3.).::(2.).::(1.)
res2: List[Double] = List(1.0, 2.0, 3.0)

scala> Nil.::(3).::(2).::(1)
res0: List[Int] = List(1, 2, 3)