CSE 341 -- Polymorphism and Higher Order Functions

Polymorphism

Polymorphism roughly means "many forms." Used in the context of functions and types, it refers to functions that can accept arguments of different types. Remember that ML is statically/strongly typed, which means that it must be able to fully type check a piece of code before executing it. This does not mean, however, that we can't define functions whose types are partially or completely flexible. Here is the most basic polymorphic function:

- fun identity(x) = x;
val identity = fn: 'a -> 'a

ML responds to this function definition that identity is a function that maps elements of any type to elements of that same type. ML makes use of type variables like 'a, 'b, 'c to refer to types of "any" type. The same symbol is used for types that are known to be identical (even though ML doesn't know what particular type they are).

Non-polymorphic operators

ML provides us with a number of operators that "destroy" polymorphism. These include:

Arithmetic operators (+, -, *, /, div, mod)
Some relational operators (>=, >, <, <=)
String concatenation (^)
Type conversion operators (ceiling, floor, real, etc.)
Boolean operators (andalso, orelse, not)

Note that some of the operators (+, -, *, and all of the above relational operators) are overloaded. This does not make them polymorphic: when they are used in an actual function or expression, ML must be able to infer the single type they refer to at compile time. For this reason we have to be explicit about the type (int or real, for instance) when we make use of these operators.

Polymorphic operators

The following built-in ML operators are all polymorphic:

Tuple constructors and accessors (#1, #2, (,..))
List constructors and accessors (::, @, hd, tl, [,..], and nil)
Equality operators (= and <>)

Here is an example of a more complicated polymorphic function:

fun append (nil, y)   = y
  | append (x::xs, y) = x::append(xs, y);

val append = fn: 'a list * 'a list -> 'a list

We can roughly see how the type inference works: From the first pattern, we see that the first argument must be a list. From the first return expression, we see that the result type must be the same as the type of the "second" argument (y). At this point, ML knows that the type of the first argument is 'a list, the type of the second argument is 'b, and the result type is 'b. At this stage, ML only knows that the type profile is 'a list * 'b -> 'b. Now, looking at the second line, we see from the result expression that an item of type 'a is being "consed" onto the recursive call of append. This lets ML conclude that 'b must be a 'a list, and it concludes that the type profile of append is 'a list * 'a list -> 'a list.

Equality Types

The operators = and <> are also polymorphic. A variable type for which = and <> are known to apply is printed ''a by ML. We call such a type an equality type. Most datatypes match equality types. However, functions provide a notable exception: any datatype that contains a function does not match an equality type. ML does not support the notion of the equality of two functions. The equality types form a subset of the the possible types in ML. By writing functions which use = or <> we restrict the set of types for which that function is applicable.

The below definition of append is only polymorphic over lists composed of equality types. Contrast this with the above append, which is polymorphic over lists composed of any types. In practice, this is not a huge deal, but it is another good reason to use pattern matching when possible.

fun append(x,y) = if x=nil then y else hd(x)::append(tl(x),y);
val append = fn: ''a list * ''a list -> ''a list

Higher Order Functions

As we discussed in the Scheme module, certain patterns/idioms of list recursion occur again and again in programming practice. Several common classes we identified were:

Mapping: Apply a function to each value in a list of values and return the list containing the results of the function applications.
Reducing: compute a single value from a list of values.
Filtering: Given a list of values and a predicate, return the list of values which satisfy that predicate.

ML, like Scheme, allows us to use higher order functions (functions which take functions as arguments) to implement the above abstractions.

Mapping/Filtering/Reducing

Map takes a unary function and a list and returns a list of the results of applying the function to every element of the list. Below is the definition of map. Notice its polymorphism.

fun map (f, nil) = nil
  | map (f, x::xs) = f(x)::map(f, xs);
val map = fn : ('a -> 'b) * 'a list -> 'b list

fun square (x:int) = x*x;
val square = fn: int -> int

fun squareList (L) = map(square, L);
val squareList = fn: int list -> int list

Reduce takes a binary function, a base value, and a list, and returns the result of applying the function "between" each list element, with the base value handling the empty list case.

fun reduce (f, base, nil)   = base
  | reduce (f, base, x::xs) = f(x, reduce(f, base, xs));
val reduce = ('a * 'b -> 'b) * 'b * 'a list -> 'b

fun sumList (L) = reduce(op +, 0, L);
val sumList = fn: int list -> int
 
fun concatList (L) = reduce (op ^, "", L);
val concatList = fn: string list -> string

Note that we use the keyword op to take built-in infix operators and pass them as prefix functions to a higher order function like reduce. There are variations on the above reduce function. For instance, try writing a reduce that combines its operands from left to right rather than right to left (as the above definition does).

Filter takes a predicate (a function that returns a boolean value) function and a list of values and returns the list of values which satisfy the predicate.

fun filter (f, nil) = nil
  | filter (f, x::xs) = if f(x) then x::filter(f, xs) else filter(f,xs);
val filter = fn : ('a -> bool) * 'a list -> 'a list

Anonymous Functions

Often, we pass "little" functions to our higher-order functions and don't wish to define an extra helper function. ML provides a mechanism for defining anonymous functions (like LAMBDAs in Scheme). As in Scheme, the anonymous functions are lexically scoped, which is to say that they have access to all local variables in enclosing scopes.

(* get all the positive integers in a list *)
fun positives (L) = filter(fn(x) => x>0, L);

(* raise every element in a list to a power *)
fun toPower(L, n) = map(fn(x) => pow(x,n), L);

Now that we know how to define anonymous functions, we see that the fun keyword is just syntactic sugar for naming an anonymous function:

(* the following are equivalent *)

fun square (x:int) = x*x;
val square = fn(x:int) => x*x;

(* to define recursive functions we use the keyword "rec" *)

fun pow (x, n) = if n=0 then 1 else x*pow(x, n-1);
val rec pow = fn(x,n) => if n=0 then 1 else x*pow(x, n-1);

(* applying an anonymous function: *)

(fn(x)=>x+1) 10;
val it = 11: int

Functions that return functions

So far, we've only seen functions that take other functions as arguments. It is possible, though, to write functions that return other functions. Here is the definition of a function that "stamps out" an incrementer function:

fun makeInc (by:int) = fn(x) => x+by;
val makeInc = fn : int -> int -> int

fun compose (f, g) = fn(x) => f(g(x));
val compose = fn : ('a -> 'b) * ('c -> 'a) -> 'c -> 'b

val incBy10 = makeInc(10);
val incBy10 = fn : int -> int

Above, we see that makeInc is a function that returns another function. Reading its type profile, we see that it is a function that takes an int, and returns a function which maps integers to integers (we know this because -> associates right to left).

Curried functions

The built-in versions of map and reduce (called fold) are actually curried, that is, they take their first argument, and return a function which takes the list argument separately. In general, defining a curried function in N arguments actually creates a function which takes just one argument and returns another curried function in N-1 arguments. We can fake a curried version of map as follows:

fun cmap (f) =         
  let
    fun temp(nil) = nil
      | temp(x::xs) = f(x) :: temp(xs)
  in
    temp
  end;

fun pow (x) =        (* less readable way to write a curried function  *)
  fn(0) => 1
  | (n) => x * pow x (n-1);

The above method for defining curried functions is pretty ugly, especially when they take more than two arguments. ML allows us to write curried functions easily by just separating the formals by spaces (rather than making the function take a tuple). Curried functions are called with spaces separating the arguments, rather than passing them a tuple of the arguments.

(* The shorthand for defining a curried power function *)
fun pow x 0 = 1
  | pow x n = x * pow x (n-1);

(* The shorthand way to defined a curried map:  *)
fun cmap f nil     = nil
  | cmap f (x::xs) = f x :: cmap f xs;
val cmap = fn : ('a -> 'b) -> 'a list -> 'b list

(* Shorthand for a curried reduce *)
fun creduce f base nil     = base
  | creduce f base (x::xs) = f(x, creduce f base xs);
val creduce = fn : ('a * 'b -> 'b) -> 'b -> 'a list -> 'b

The nice thing about curried functions is that we can partially instantiate them to create other interesting functions. This is something we can't do when a function takes a tuple, because we need to know all of the arguments when we call the function. We partially instantiate a curried function by passing it just some of its parameters (often just the first one), and using the resulting function in some other computation. (It is only possible to partially instantiate functions starting from the left in the argument list, however.)

val listInc = cmap(fn(x) => x+1);
val listInc = fn: int list -> int list

val powOf2 = pow 2;
val powOf2 = fn: int -> int

listInc([1,2,3]);
val it = [2,3,4] : int list

powOf2 10;
val it = 1024 : int

dugan@cs.washington.edu (Last Update: )