Type Inference, Annotations & Polymorphism

OCaml infers the most general type of every expression:

10.1 Hindley–Milner inference

OCaml infers the most general type of every expression:

'a, 'b are type variables (read "alpha", "beta") — this is parametric polymorphism (generics).

let id x = x                 (* val id : 'a -> 'a *)
let pair x y = (x, y)        (* val pair : 'a -> 'b -> 'a * 'b *)
let apply f x = f x          (* val apply : ('a -> 'b) -> 'a -> 'b *)

10.2 Type annotations

let add (x : int) (y : int) : int = x + y
let f = (fun x -> x : int -> int)
let (xs : string list) = []

10.3 Type aliases

type point = float * float
type 'a pair = 'a * 'a
type ('k, 'v) assoc = ('k * 'v) list

10.4 Reading function types

takes int, returns int int -> int -> int takes two ints (curried) (int -> int) -> int takes a function 'a list -> int polymorphic over element type ?sep:string -> string list -> string optional labeled arg f:('a -> 'b) -> 'a list -> 'b list

10.5 Weak type variables & the value restriction (preview)

'_weak1 is not polymorphic: it will be fixed by its first use. Details in §29.

let r = ref []         (* val r : '_weak1 list ref *)

10.6 Common type errors

Read errors carefully: "This expression has type X but an expression was expected of type Y".

1 + 2.0
(* Error: This expression has type float but an expression was expected of type int *)

"a" ^ 1
(* Error: This expression has type int but ... string *)

🧪 Part I Exercises

Write power : int -> int -> int computing x^n tail-recursively.

Write last : 'a list -> 'a option.

Write rev : 'a list -> 'a list in O(n).

Write range : int -> int -> int list (inclusive), tail-recursive.

Write compress that removes consecutive duplicates: [1;1;2;3;3;3;1] -> [1;2;3;1].

Implement flatten : 'a list list -> 'a list.

Implement gcd using Euclid's algorithm.

Write is_palindrome : 'a list -> bool.

Implement FizzBuzz printing 1..100 using match on a tuple (n mod 3, n mod 5).

Write collatz_steps : int -> int.