The importance of polymorphic types and functions is that they let us write shorter, clearer programs. It's similar to the way Pascal procedures let us use the same code to operate on different data values, but much more powerful. We can write a single Hope function to reverse a list of numbers or characters, where we'd need to write two identical Pascal subroutines to reverse an array of integers and an array of characters.
We can use polymorphic functions whenever we're concerned only with the arrangement of the objects in a data structure and not with their values. Sometimes, we'll want to apply some function to the primitive data items in the structure. Here's a function that uses a second function square to define a list (num) whose elements are the squares of another list (num):
dec square : num -> num ;
--- square ( n ) <= n * n ;
dec squarelist : list ( num ) -> list ( num ) ;
--- squarelist ( nil ) <= nil ;
--- squarelist ( n :: l ) <= square ( n ) :: squarelist ( l ) ;
Every time we write a function to process every element of a list, we'll
write something almost identical to squarelist. Here's a function to
define a list of factorials:
dec fact : num -> num ;
--- fact ( 0 ) <= 1 ;
--- fact ( succ ( n ) ) <= succ ( n ) * fact ( n ) ;
dec factlist : list ( num ) -> list ( num ) ;
--- factlist ( nil ) <= nil ;
--- factlist ( n :: l ) <= fact ( n ) :: factlist ( l ) ;
factlist has exactly the same `shape' as squarelist, it just applies
fact instead of square and then applies itself recursively. Values that
differ between applications are usually supplied as actual parameters. Hope
treats functions as data objects, so we can do this in a perfectly natural
way. A function that can take another function as an actual parameter is
called a higher-order function. When we declare it we must give the type of
formal parameter standing for the function in the usual way. The declaration
of fact tells us that it's:
num -> num
Read this as `a function mapping numbers to numbers'. Now let's see how we
can use this idea to write factlist and squarelist as a single higher-
order function. The new function needs two parameters, the original list,
and the function that's applied inside it. Its declaration will be:
dec alllist : list ( num ) # ( num -> num ) -> list ( num ) ;
The `shape' of alllist will be the same as factlist and squarelist, but
the function we apply to each element of the list will be the formal
parameter:
--- alllist ( nil, f ) <= nil ;
--- alllist ( n :: l, f ) <= f ( n ) :: alllist ( l, f ) ;
We use alllist like this:
alllist ( [ 2,4,6 ], square ) ;
[ 4,16,36 ] : list ( num )
alllist ( [ 2,4,6 ], fact ) ;
[ 2,24,720 ] : list ( num )
Notice that there's no argument list after square or fact in the
application of alllist, so this construction won't be confused with
functional composition. fact( 3 ) represents a function application, but
fact by itself represents the unevaluated function.
Higher-order functions can also be polymorphic. We can use this idea to write a more powerful version of alllist that will apply an arbitrary function to every element of a list of objects of arbitrary type. This version of the function is usually known as map:
typevar alpha, beta ;
dec map : list ( alpha ) # ( alpha -> beta ) -> list ( beta ) ;
--- map ( nil, f ) <= nil ;
--- map ( n :: l, f ) <= f ( n ) :: map ( l, f ) ;
The definition now uses two type variables alpha and beta. Each one
represents the same actual type throughout one instance of map, but the two
types can be different. This means we can use any function that maps alphas
to betas to generate a list of betas from any list of alphas.
The actual types aren't restricted to scalars, which makes map rather more powerful than we might realise at first sight. Suppose we've got a suitably polymorphic function that finds the length of a list:
typevar gamma ;
dec length : list ( gamma ) -> num ;
--- length ( nil ) <= 0 ;
--- length ( n :: l ) <= 1 + length ( l ) ;
length ( [ 2,4,6,8 ] ) + length ( "cat" ) ;
7 : num
We can use map to apply length to every element of a list of words
defined by wordlist:
map ( wordlist ( "The form remains, the function never dies" ), length ) ;
[ 3,4,8,3,8,5,4 ] : list ( num )
In this example alpha is taken to be a list ( char ) and beta to be a
num, so the type of the function must be ( list ( char ) -> num ). length
fits the bill if gamma is taken to be a character.