CSC448: Type Checking Revisited: Generic Polymorphism I [111/133]

Consider an ML function to reverse a list:

fun reverse [] = []
|   reverse (x::xs) = (reverse xs) @ [x]; 
        

ML infers the type 'a list -> 'a list for reverse:

> val 'a reverse = fn : 'a list -> 'a list
        

And we can apply reverse to lists of different types:

- reverse [1,2,3];
> val it = [3, 2, 1] : int list

- reverse ["hello", "world"];
> val it = ["world", "hello"] : string list
        

The type 'a list -> 'a list means that for any type T, we can use reverse with type T list -> T list. For example, we can use reverse with type int list -> int list or with type string list -> string list.