Generic Programming & Polymorphism

The word polymorphism covers three genuinely different ideas that are often conflated. Separating them is the first step to mastery.

Parametric polymorphism: A single piece of code works uniformly for any type, with no knowledge of what that type is. The classic example is the identity function: id(x) = x. It works for integers, strings, lists, functions — anything. The code doesn't branch on the type; it truly doesn't care. In Haskell this is id :: a -> a. In Java, <T> T id(T x). In C++, template<typename T> T id(T x).

Ad-hoc polymorphism: A function name is reused for different implementations depending on the type. When you write x + y, the behavior is completely different for integers (hardware ADD instruction) vs. floats (IEEE 754 floating-point add) vs. strings (concatenation). Each type contributes its own implementation. This is also called overloading.

Subtype polymorphism: A value of type Dog can be used wherever a value of type Animal is expected, because Dog is a subtype. This module only touches this briefly; it is the subject of the inheritance and OOP modules.

A key insight from type theory: parametric polymorphism is free theorems — the type signature alone constrains what a function can possibly do. A function of type ∀a. [a] -> [a] in Haskell must return a permutation/sublist of its input; it cannot construct values of type a from thin air. Ad-hoc polymorphism breaks this: a function constrained to Ord a => a -> a -> a could choose between min or max or something type-specific.

-- Haskell: parametric polymorphism
id :: a -> a          -- works for ANY type a
id x = x

length :: [a] -> Int  -- works for lists of anything
length [] = 0
length (_:xs) = 1 + length xs

-- Ad-hoc polymorphism via type class
class Describable a where
  describe :: a -> String

instance Describable Int where
  describe n = "Int: " ++ show n

instance Describable Bool where
  describe True  = "It's true!"
  describe False = "It's false!"

A generic function is one that is parameterized by a type, just as a regular function is parameterized by a value. The type parameter T is a variable that ranges over types.

Consider a Pair container. Without generics, you'd write IntPair, StringPair, FloatPair... With generics, you write Pair<T, U> once. The type checker enforces that you don't accidentally put an Int where you expected a String.

The key insight is that the implementation is written once, but the type checker instantiates it at every call site. When you call swap(pair<int, string>), the compiler checks that your usage is consistent with the single generic definition.

This is type-safe because the compiler rejects programs where types don't match, unlike the old C trick of passing void* everywhere, which compiles but silently corrupts memory at runtime.

The mathematical foundation is System F (Girard, Reynolds, 1970s): a typed lambda calculus with explicit type abstraction (Λa. term) and type application (term [Int]). Every generic function is a term in System F. Haskell's type system is essentially System F with type inference added.

// C++ generic Pair
template<typename T, typename U>
struct Pair {
    T first;
    U second;
};

template<typename T, typename U>
Pair<U, T> swap_pair(Pair<T, U> p) {
    return {p.second, p.first};
}

// Usage — compiler instantiates for each concrete type
Pair<int, std::string> p = {42, "hello"};
Pair<std::string, int> q = swap_pair(p);
// q.first == "hello", q.second == 42

// Java equivalent
public class Pair<T, U> {
    public T first;
    public U second;
    public Pair(T first, U second) {
        this.first = first; this.second = second;
    }
}

Pair<Integer, String> p = new Pair<>(42, "hello");

The compiler has to do something with a generic function — it must eventually generate machine code. There are two fundamentally different strategies. Monomorphization generates a separate concrete copy of the code for each distinct type it is instantiated with.

When you write max<int>(a, b) and max<double>(x, y), the compiler generates two distinct machine-code functions: one that operates on 32-bit integers and one on 64-bit doubles. The generic source is a template — it is never compiled directly, only when instantiated.

Performance: Monomorphization is zero-cost. Each instantiation is as fast as hand-written code for that specific type. The compiler can inline, auto-vectorize, and optimize each version independently. This is why C++ templates and Rust generics have no runtime overhead compared to hand-specialized code.

Cost: Code bloat. If sort<T> is instantiated for 50 different types, you get 50 copies of the sort code in your binary. In practice, linkers can deduplicate identical instantiations, but this is still a real concern in large codebases.

Error messages: Type errors are reported at instantiation time, not at definition time. This is the infamous source of C++ template error messages that span hundreds of lines — the compiler is unrolling instantiation chains.

Rust uses monomorphization for all generic functions marked with concrete trait bounds. fn largest<T: PartialOrd>(list: &[T]) -> &T becomes one machine-code function per type T you call it with.

// Rust: monomorphized generics
fn largest<T: PartialOrd>(list: &[T]) -> &T {
    let mut largest = &list[0];
    for item in list {
        if item > largest {
            largest = item;
        }
    }
    largest
}

fn main() {
    let numbers = vec![34, 50, 25, 100, 65];
    // Compiler generates largest_i32 machine code
    println!("{}", largest(&numbers));

    let chars = vec!['y', 'm', 'a', 'q'];
    // Compiler generates largest_char machine code
    println!("{}", largest(&chars));
}
// Two separate machine-code functions are emitted

The alternative strategy is type erasure: compile generics into a single piece of machine code that works for all types, by replacing type parameters with a common representation (usually a pointer/reference, since all heap-allocated objects have the same size in memory).

In Java, List<String> and List<Integer> compile to the same bytecode — List with all T replaced by Object. The compiler inserts casts at call sites to recover the original type, and checks these casts at runtime. The generic type information is erased after the type-checking phase.

Upside: Single compiled representation, smaller code size, compatible with reflection and other runtime type machinery.

Downside 1 — Performance: Every value must be boxed (heap-allocated) to be passed as Object. List<Integer> cannot hold raw int values; each integer is wrapped in an Integer object with heap overhead. This adds GC pressure and cache misses. (Java is adding value-type generics via Project Valhalla to fix this.)

Downside 2 — Reification: You cannot ask at runtime "what is T?" in Java. new T() is illegal; instanceof T is illegal; T[] is illegal. This surprises beginners constantly.

Go's approach (pre-1.18): Go had no generics at all — you used interface{} everywhere and cast manually. Go 1.18 added generics with a hybrid approach: monomorphization for types with different pointer shapes, shared implementation (GC shape stenciling) for types with the same shape.

// Java type erasure in action
import java.util.*;

public class TypeErasureDemo {
    // At compile time: List<String> and List<Integer> are distinct
    // At runtime: BOTH are just List (raw type)
    public static void main(String[] args) {
        List<String> strings = new ArrayList<>();
        List<Integer> ints = new ArrayList<>();

        // This is true at runtime — types are ERASED
        System.out.println(
            strings.getClass() == ints.getClass()  // prints: true
        );

        // Compiler inserts implicit cast here:
        strings.add("hello");
        String s = strings.get(0);  // compiled as: (String) strings.get(0)

        // ILLEGAL — cannot use T in runtime context:
        // T obj = new T();       // compile error
        // if (x instanceof T) {} // compile error
    }
}

Pure parametric polymorphism is powerful but limited: if T can be anything, you can't call any methods on values of type T. You can only pass them around.

Bounded type parameters let you require that T satisfies some interface or constraint. This is the bridge between parametric and ad-hoc polymorphism.

In Java: <T extends Comparable<T>> means T must implement the Comparable interface. Now you can call a.compareTo(b) on values of type T.

In C++ (pre-C++20): you wrote unconstrained templates and got cryptic errors if the type didn't support the required operations. C++20 Concepts fix this: template<typename T> requires std::totally_ordered<T> documents and enforces the constraint at the point of instantiation.

In Rust: fn f<T: Display + Clone>(x: T) — T must implement both the Display and Clone traits. The compiler checks this at the call site.

In Haskell: sort :: Ord a => [a] -> [a] — a must be an instance of the Ord type class.

The key principle: a bounded type parameter gives you a contract — a set of operations you can perform on any value of that type. The generic code is written against the contract; the concrete type satisfies the contract.

// Java: bounded type parameter
public class BoundedDemo {
    // T must implement Comparable<T>
    public static <T extends Comparable<T>> T max(T a, T b) {
        return a.compareTo(b) >= 0 ? a : b;
    }

    // Multiple bounds: T extends both Comparable and Serializable
    public static <T extends Comparable<T> & java.io.Serializable>
    T maxSerializable(T a, T b) {
        return a.compareTo(b) >= 0 ? a : b;
    }
}

// C++20 Concepts
#include <concepts>
template<std::totally_ordered T>
T cpp_max(T a, T b) {
    return a >= b ? a : b;
}

// Rust trait bounds
use std::fmt::Display;
fn print_larger<T: PartialOrd + Display>(a: T, b: T) {
    if a > b { println!("{}", a); }
    else      { println!("{}", b); }
}

Function overloading allows multiple functions with the same name but different parameter types. The compiler selects the right version at compile time based on the types of the arguments. This is resolved statically — there is no runtime dispatch.

Overloading is pervasive: + in C++ is overloaded for int, double, std::string. print in many languages is overloaded for all printable types.

Resolution rules vary by language and are a notorious source of confusion. In C++, overload resolution involves: exact matches, promotions (e.g. char to int), standard conversions, user-defined conversions, and variadic matches — in that priority order. When multiple overloads are equally viable, the call is ambiguous and fails to compile.

Overloading vs. overriding: Overloading is compile-time selection among multiple functions by signature. Overriding is runtime dispatch when a subclass replaces a parent method — that is subtype polymorphism, not overloading.

Operator overloading is the same mechanism applied to operators. Python's __add__, C++'s operator+, Haskell's Num type class — all let you give custom meaning to + for your types. Abuse of operator overloading (making * mean "apply transformation" on a matrix class, or making << mean "append to") leads to unreadable code. Use it to express natural mathematical operations.

#include <iostream>
#include <string>
using namespace std;

// Three overloads of 'add' — different signatures
int add(int a, int b)           { return a + b; }
double add(double a, double b)  { return a + b; }
string add(string a, string b)  { return a + b; }

// Operator overloading
struct Vec2 {
    double x, y;
    Vec2 operator+(const Vec2& o) const {
        return {x + o.x, y + o.y};
    }
    // ostream operator for printing
    friend ostream& operator<<(ostream& os, const Vec2& v) {
        return os << "(" << v.x << ", " << v.y << ")";
    }
};

int main() {
    cout << add(1, 2)           << endl;  // calls int version
    cout << add(1.5, 2.5)       << endl;  // calls double version
    cout << add("hi", " there") << endl;  // calls string version

    Vec2 a{1, 2}, b{3, 4};
    cout << a + b << endl;  // calls operator+, prints (4, 6)
}

Raw overloading has a problem: it's hard to abstract over. You can't write a function that says "I need any type that supports add" and have it checked at definition time. Type classes (Haskell) and traits (Rust) solve this.

A type class is a named collection of operations that a type must provide to be a member. It is a contract at the type level. class Eq a where (==) :: a -> a -> Bool says: type a is in the Eq class if it provides an == function with that signature.

An instance provides the implementation: instance Eq Int where (==) = primEqInt.

Functions can be written against a type class constraint: nub :: Eq a => [a] -> [a] removes duplicates from any list whose elements support equality. The constraint is checked when you call nub with a specific type.

Traits in Rust are essentially the same idea, but Rust integrates them with ownership and lifetime checking. A trait defines a set of methods; a type implements the trait by providing those methods; generic functions can require trait bounds.

Why this beats raw overloading:

1. Coherence: In Haskell/Rust, there is at most one implementation of a type class/trait for a given type in a given scope. No ambiguity.
2. Abstraction: You can write fn largest<T: Ord>(...) and reason about what it can do purely from the constraints.
3. Default implementations: Type classes can provide default implementations in terms of other required methods, reducing boilerplate.

-- Haskell type class example

-- Define a type class
class Container f where
    empty  :: f a
    insert :: a -> f a -> f a
    toList :: f a -> [a]

-- Stack is an instance of Container
newtype Stack a = Stack [a]

instance Container Stack where
    empty            = Stack []
    insert x (Stack xs) = Stack (x:xs)
    toList (Stack xs)   = xs

-- Generic function using the type class constraint
fromList :: Container f => [a] -> f a
fromList = foldr insert empty

-- Works for Stack (and any other Container instance)
myStack :: Stack Int
myStack = fromList [1, 2, 3]
-- toList myStack == [3, 2, 1]

When you have generics and subtyping, a subtle question arises: if Dog is a subtype of Animal, what is the relationship between List<Dog> and List<Animal>?

Intuitively, a List<Dog> sounds like it should be usable as a List<Animal> — after all, you can read Animal objects from it. But if you could write to it (add any Animal), you could insert a Cat, breaking the invariant that it contains only Dogs. This is the core tension.

Covariance (out T in Kotlin/C#, ? extends T in Java): Container<Dog> is a subtype of Container<Animal>. Safe when you only read from the container.

Contravariance (in T in Kotlin/C#, ? super T in Java): Container<Animal> is a subtype of Container<Dog>. Safe when you only write to the container (you can write a Dog where any Animal is accepted).

Invariance: No subtyping relationship. List<Dog> and List<Animal> are unrelated. Java arrays are (unsoundly) covariant — Dog[] is a subtype of Animal[] — but this requires a runtime check on every array write and can throw ArrayStoreException.

The PECS principle (Produce Extends, Consume Super) in Java: use ? extends T for containers you only read from (producers), and ? super T for containers you only write to (consumers). Collections.copy(dest, src) uses both: src is ? extends T, dest is ? super T.

// Java variance with wildcards
import java.util.*;

public class VarianceDemo {
    // Covariant: read-only, accepts List<Dog>, List<Animal>, etc.
    static double sumWeights(List<? extends Animal> animals) {
        double total = 0;
        for (Animal a : animals) total += a.getWeight();
        return total;
        // animals.add(new Cat()); // COMPILE ERROR — cannot write
    }

    // Contravariant: write-only, accepts List<Animal>, List<Object>
    static void addDogs(List<? super Dog> list) {
        list.add(new Dog("Rex"));
        // Dog d = list.get(0); // COMPILE ERROR — cannot read as Dog
    }

    // PECS: Collections.copy signature
    // static <T> void copy(List<? super T> dest,
    //                      List<? extends T> src)
}

Generic programming shines in data structures. The standard library of every modern language is built on generic containers: Vec<T>, HashMap<K,V>, Option<T>, Result<T,E>.

Designing a generic data structure requires thinking about:

1. What type parameters do you need? A stack needs one (T). A map needs two (K, V). An error-handling type needs two (Ok, Err).

2. What constraints do you need? A stack needs nothing — you just store and retrieve. A sorted set needs T: Ord. A hashmap needs K: Hash + Eq.

3. What operations do you expose? Generic methods on the struct may introduce additional type parameters beyond the struct's own.

A powerful pattern is phantom types: using a type parameter purely to carry compile-time information, with no runtime representation. A classic example is a Meters<T> type that prevents accidentally adding meters to seconds — the type checker enforces dimensional consistency with zero runtime cost.

// Rust: generic stack with trait bounds
struct Stack<T> {
    elements: Vec<T>,
}

impl<T> Stack<T> {
    fn new() -> Self { Stack { elements: vec![] } }
    fn push(&mut self, item: T) { self.elements.push(item); }
    fn pop(&mut self) -> Option<T> { self.elements.pop() }
    fn is_empty(&self) -> bool { self.elements.is_empty() }
}

// Additional method only when T: Display
use std::fmt::Display;
impl<T: Display> Stack<T> {
    fn print_top(&self) {
        match self.elements.last() {
            Some(top) => println!("Top: {}", top),
            None => println!("Stack is empty"),
        }
    }
}

// Phantom type for compile-time units
use std::marker::PhantomData;
struct Length<Unit> {
    value: f64,
    _unit: PhantomData<Unit>,
}
struct Meters;
struct Feet;

impl Length<Meters> {
    fn new(v: f64) -> Self { Length { value: v, _unit: PhantomData } }
}
// Length<Meters> and Length<Feet> are DIFFERENT types — cannot add them

When a method is called on a generic or polymorphic type, the runtime must somehow find the right implementation. There are two strategies:

Static dispatch (monomorphization, inlining): The compiler knows the concrete type at compile time and either inlines the call or generates a direct call to the specific function. Zero runtime overhead. This is how C++ templates and Rust generics work by default.

Dynamic dispatch (virtual dispatch, vtable): The runtime looks up the correct implementation in a table at call time. This costs one pointer dereference per call and prevents inlining. In C++ this is virtual methods; in Rust this is dyn Trait; in Java/Python, almost all method calls are dynamically dispatched.

Trait objects in Rust: &dyn Draw is a fat pointer — it stores both a pointer to the data and a pointer to a vtable (a table of function pointers for the Draw trait). This enables runtime polymorphism: you can have a Vec<Box<dyn Draw>> containing circles, rectangles, and triangles, all drawn with the same call.

The trade-off: Static dispatch is faster but requires knowing the type at compile time and may cause code bloat. Dynamic dispatch is flexible (you can have heterogeneous collections) but pays a runtime cost.

In practice: prefer static dispatch by default; use dynamic dispatch when you genuinely need a heterogeneous collection or when the code-size costs of monomorphization are unacceptable.

// Rust: static vs. dynamic dispatch
trait Draw {
    fn draw(&self);
}

struct Circle { radius: f64 }
struct Rectangle { width: f64, height: f64 }

impl Draw for Circle {
    fn draw(&self) { println!("Drawing circle r={}", self.radius); }
}
impl Draw for Rectangle {
    fn draw(&self) { println!("Drawing {}x{} rect", self.width, self.height); }
}

// STATIC dispatch — compiler generates draw_circle, draw_rect separately
fn draw_static<T: Draw>(shape: &T) {
    shape.draw();  // inlined, zero overhead
}

// DYNAMIC dispatch — single function, vtable lookup at runtime
fn draw_dynamic(shape: &dyn Draw) {
    shape.draw();  // pointer dereference + call through vtable
}

fn main() {
    let shapes: Vec<Box<dyn Draw>> = vec![
        Box::new(Circle { radius: 3.0 }),
        Box::new(Rectangle { width: 4.0, height: 5.0 }),
    ];
    for s in &shapes { draw_dynamic(s.as_ref()); }
}

A regular generic type parameter ranges over types: T could be Int, String, List<Int>, etc. A higher-kinded type parameter ranges over type constructors: type-level functions that take a type and produce a type.

List itself is not a type — it is a type constructor of kind * -> *: give it Int and you get List<Int>. Similarly Map has kind * -> * -> *.

Haskell's Functor type class is the canonical example of a higher-kinded abstraction:

class Functor f where
  fmap :: (a -> b) -> f a -> f b

Here f is not a type — it is a type constructor of kind * -> *. Maybe, List, Either e, and IO are all instances of Functor. A single function fmap works for all of them.

Java and C# lack higher-kinded types — you cannot abstract over List<?> and Optional<?> simultaneously with a single generic interface. This is a fundamental expressivity limitation.

Scala has higher-kinded types. Haskell has them natively. Rust approximates them with associated types and GATs (Generic Associated Types, stabilized in Rust 1.65).

For a CS student: understanding higher-kinded types deepens your appreciation of what type systems can and cannot express, and explains why certain abstractions (monads, functors, applicatives) are natural in Haskell but require significant boilerplate in Java.

-- Haskell: Functor — higher-kinded type class
class Functor f where
  fmap :: (a -> b) -> f a -> f b

-- f = Maybe  (kind * -> *)
instance Functor Maybe where
  fmap _ Nothing  = Nothing
  fmap g (Just x) = Just (g x)

-- f = []  (list, kind * -> *)
instance Functor [] where
  fmap = map

-- One function, works for ANY Functor
applyTwice :: Functor f => (a -> a) -> f a -> f a
applyTwice g = fmap g . fmap g

-- applyTwice (+1) (Just 3)  == Just 5
-- applyTwice (*2) [1,2,3]   == [4,8,12]
-- applyTwice (+1) Nothing   == Nothing

Understanding the theory lets you design better APIs. Several patterns emerge repeatedly:

Policy-based design (C++ templates): Decompose a class's behavior into orthogonal policies and pass them as template parameters. A SmartPtr<T, DeletionPolicy, ThreadPolicy> is customizable at compile time with zero overhead. Popularized by Andrei Alexandrescu in Modern C++ Design.

CRTP (Curiously Recurring Template Pattern): class Derived : public Base<Derived>. The base class receives its derived type as a template argument, enabling static polymorphism (compile-time dispatch without virtual functions). Used for mixins that need to call derived-class methods without virtual dispatch.

Type-safe builder pattern: Use phantom types to enforce state machines at compile time. A Connection<Uninitialized> can only call connect(), which returns a Connection<Connected>, which alone can call send(). The state machine is enforced by the type checker with zero runtime cost.

Monadic error handling: Result<T, E> in Rust / Either e a in Haskell / Option<T> — generic types that represent computations that may fail. The ? operator in Rust and >>= in Haskell are generic operations that chain these computations, propagating errors automatically without exceptions.

The unifying theme: use the type system to make illegal states unrepresentable. Generic types let you encode invariants that would otherwise require runtime checks.

// Rust: type-state pattern (phantom types enforce protocol)
use std::marker::PhantomData;

struct Locked;
struct Unlocked;

struct Safe<State> {
    combination: u32,
    contents: String,
    _state: PhantomData<State>,
}

impl Safe<Locked> {
    fn new(combo: u32) -> Self {
        Safe { combination: combo,
               contents: String::new(),
               _state: PhantomData }
    }
    fn unlock(self, combo: u32) -> Result<Safe<Unlocked>, Safe<Locked>> {
        if combo == self.combination {
            Ok(Safe { combination: self.combination,
                      contents: self.contents,
                      _state: PhantomData })
        } else { Err(self) }
    }
}

impl Safe<Unlocked> {
    fn store(&mut self, item: &str) { self.contents = item.to_string(); }
    fn lock(self) -> Safe<Locked> {
        Safe { combination: self.combination,
               contents: self.contents,
               _state: PhantomData }
    }
}
// safe.store("jewels") on a Locked safe: COMPILE ERROR