What? Why?

fun quickSort(collection: CollectionOfInts) { ... }
quickSort(listOf(1, 2, 3))          // OK
quickSort(listOf(1.0, 2.0, 3.0))    // NOT OK

fun quickSort(collection: CollectionOfDoubles) { ... } // overload
quickSort(listOf(1.0, 2.0, 3.0))    // OK 
quickSort(listOf(1, 2, 3))          // OK

Kotlin Number inheritors: Int, Double, Byte, Float, Long, Short
Do we need 4 more implementations of quickSort?

How?

Does the quickSort algorithm actually care what is it sorting?
No, as long as it can compare two values against each other.

fun <T : Comparable<T>> quickSort(collection: Collection<T>): Collection<T> { ... }

quickSort(listOf(1.0, 2.0, 3.0))            // OK 

quickSort(listOf(1, 2, 3))                  // OK

quickSort(listOf("one", "two", "three"))    // OK

Type Parameters

A type parameter is a placeholder for a type, resolved at the call site.

Generics let you write code that works with any type
or any type satisfying a constraint
without duplicating it

class Holder<T>(val value: T) { ... }

val intHolder = Holder<Int>(23)

val cupHolder = Holder("cup")   // Generic parameter type can be inferred

Constraints

An upper bound constrains a type parameter to a specific type or its subtypes - ensuring the type provides the required functionality.

class Pilot<T : Movable>(val vehicle: T) { 
    fun go() { vehicle.move() }
}

val ryanGosling = Pilot<Car>(Car("Chevy", "Malibu"))
val sullySullenberger = Pilot<Plane>(Plane("Airbus", "A320"))

Constraints #2

There can be several parameter types, and generic classes can participate in inheritance

public interface MutableMap<K, V> : Map<K, V> { ... }

There can also be several constraints (meaning the type parameter has to implement several interfaces):

fun <T, S> moveInAnAwesomeWayAndCompare(a: T, b: S) 
    where T: Comparable<T>, S: Comparable<T>, T: Awesome, T: Movable 
    { ... }

Star-projection

When you do not care about the parameter type, you can use star-projection * (Any? / Nothing). For example, all maps have the same size:Int property, independent of their specific generic parameters

fun printKeys(map: MutableMap<*, *>) { ... }

Note: Working with methods that actually use generic parameters is almost impossible when using star-projection. For example, MutableList<*> will have add(element: Nothing) and get(index: Int): Any?

Back to Subtyping

open class A
open class B : A()
class C : B()

Nothing <: C <: B <: A <: Any

This means that the Any is the superclass for all the classes
At the same time Nothing is a subtype of any type

Note: <: is standard notation for "is a subtype of" in type theory, but in Kotlin we use :

Variance problem

a.k.a. Does subtyping carry over?

interface Holder<T> {
    fun push(newValue: T)   // consumes an element

    fun pop(): T            // produces an element

    fun size(): Int         // does not interact with T
}

Can we assign Holder<Int> to Holder<String>?
What about Holder<Int> to Holder<Number>?

How relationship between types A and B affects the relationship between Holder<A> and Holder<B>?

Variance annotations

interface Holder<T> {
    fun push(newValue: T)   // consumes an element
    fun pop(): T            // produces an element
    fun size(): Int         // does not interact with T
}

Variance modifiers:

G<T> - invariant, can consume and produce elements
G<in T> - contravariant, can only consume elements
G<out T> - covariant, can only produce elements
G<*> - star-projection, does not interact with T

Splitting Holder<T> by role allows the compiler to enforce safe subtype relationships

Variance example #1

G<T> // invariant, can consume and produce elements

interface Holder<T> {
    fun push(newValue: T) // consumes an element: OK

    fun pop(): T // produces an element: OK

    fun size(): Int // does not interact with T: OK
}

Variance example #2

G<in T> // contravariant, can only consume elements

interface Holder<in T> {
    fun push(newValue: T) // consumes an element: OK

    fun pop(): T // produces an element: ERROR: [TYPE_VARIANCE_CONFLICT_ERROR] 
                 // Type parameter T is declared as 'in' but occurs in 'out' position in type T

    fun size(): Int // does not interact with T: OK
}

Variance example #3

G<out T> // covariant, can only produce elements

interface Holder<out T> {
    fun push(newValue: T) // consumes an element: ERROR: [TYPE_VARIANCE_CONFLICT_ERROR] 
                        // Type parameter T is declared as 'out' but occurs in 'in' position in type T

    fun pop(): T // produces an element: OK

    fun size(): Int // does not interact with T: OK
}

Variance example #4

interface Holder<T> {
    fun push(newValue: T) // consumes an element: OK
    fun pop(): T // produces an element: OK
    fun size(): Int // does not interact with T: OK
}

fun <T> foo1(holder: Holder<T>, t: T) {
    holder.push(t) // OK
}

fun <T> foo2(holder: Holder<*>, t: T) {
    holder.push(t) // ERROR: [TYPE_MISMATCH] Type mismatch. Required: Nothing. Found: T
}

Star-projection makes the input type Nothing - you can never safely call a consuming method on Holder<*>

Subtyping and variance

open class A
open class B : A()      —--->  Nothing <: C <: B <: A <: Any
class C : B()

class Holder<T>(val value: T) { ... }

Holder<Nothing> ??? Holder<C> ??? Holder<B> ??? Holder<A> ??? Holder<Any>