CSc 372 - Comparative Programming Languages
10 : Haskell -- Polymorphic Functions

Christian Collberg

Department of Computer Science

University of Arizona

1 Polymorphic Functions

In many languages we can't write a generic sort routine, i.e. one that can sort arrays of integers as well as arrays of reals:
$\begin{gprogram} {\bf procedure} Sort (\\ \xx {\bf var} A : {\bf array of} <type>; \\ \xx n : integer); \end{gprogram}$
In Haskell (and many other FP languages) we can write polymorphic (``many shapes'') functions.
Functions of polymorphic type are defined by using type variables in the signature:
$\begin{gprogram} length :: [a] -> Int \\ length s = ... \end{gprogram}$

2 Polymorphic Functions...

length is a function from lists of elements of some (unspecified) type a, to integer. I.e. it doesn't matter if we're taking the length of a list of integers or a list of reals or strings, the algorithm is the same.
$\begin{gprogram} length [1,2,3] \xxxxxxx $\Rightarrow$\ 3 (list of Int) \\ le... ...g) \\ length ''Hi!'' \xxxxxxx $\Rightarrow$\ 3 (list of Char) \end{gprogram}$

3 Polymorphic Functions...

We have already used a number of polymorphic functions that are defined in the standard prelude.
head is a function from ``lists-of-things'' to ``things'':
$\begin{gprogram} \xx head :: [a] -> a \end{gprogram}$
tail is a function from lists of elements of some type , to a list of elements of the same type:
$\begin{gprogram} \xx tail :: [a] -> [a] \end{gprogram}$
cons "(:)" takes two arguments: an element of some type a and a list of elements of the same type. It returns a list of elements of type a:
$\begin{gprogram} \xx (:) :: a -> [a] -> [a] \end{gprogram}$

4 Polymorphic Functions...

Note that head and tail always take a list as their argument. tail always returns a list, but head can return any type of object, including a list.
Note that it is because of Haskell's strong typing that we can only create lists of the same type of element. If we tried to do
$\begin{gprogram} \xx \redtxt{? 5 : [True]} \end{gprogram}$
the Haskell type checker would complain that we were consing an Int onto a list of Bools, while the type of ``:'' is
$\begin{gprogram} \xx (:) :: a -> [a] -> [a] \end{gprogram}$

Context Predicates

5 The `remdups` Function

Remember the remdups function:
$\begin{gprogram} remdups [1] \xxxxxxx $\Rightarrow$\ [1] \\ remdups [1,2,1] \... ...\ [1,2,2] \\ remdups [1,1,1,2] \xxxxxxx $\Rightarrow$\ [1,2,1] \end{gprogram}$
Algorithm in Haskell:

$\begin{gprogram} remdups :: [Int] -> [Int] \\ remdups x:y:xs = \\ \x if x == y... ...arrow$\ case 2 \\ remdups xs = xs \xxxxxxxx $\Leftarrow$\ case 3 \end{gprogram}$

6 Context Predicates

Obviously remdups should work for any list, not just lists of Ints. Removing duplicates from a list of strings is no different from removing duplicates from a list of integers.
However, there's a complication. In order to remove duplicates from a list, we must be able to compare list elements for equality.
The polymorphic type
$\begin{gprogram} \xx [a] -> [a] \end{gprogram}$
is therefore a bit too general, since it would allow any type, even one for which equality is not defined.

7 Context Predicates...

Haskell uses context predicates to restrict polymorphic types:
$\begin{gprogram} remdups :: Eq [a] => [a] -> [a] \end{gprogram}$
Now, remdups may only be applied to list of elements where the element type has == and = defined.
Eq is called a type class. Ord is another useful type class. It is used to restrict the polymorphic type of a function to types for which the relational operators (<, <=, >, >=) have been defined.

8 Multiple Context Predicates

Consider the signum Function:
$\begin{gprogram} signum :: (Num a, Ord a) => a -> Int \\ signum n \xxx \vert \x... ... \xxx \vert \x n > 0 \xxx = 1 \\ \xxx \vert \x n < 0 \xxx = -1 \end{gprogram}$
signum can be applied to any type that is a number (hence the Num a predicate), and for which the relational operators are defined (Ord a).
Without these restrictions, the polymorphic signum function could have been applied to lists, for example, which would not have made sense.

Conclusion

9 Summary...

We want to define functions that are as reusable as possible.
1. Polymophic functions are reusable because they can be applied to arguments of different types.
2. Curried functions are reusable because they can be specialized; i.e. from a curried function f we can create a new function f' simply by ``plugging in'' values for some of the arguments, and leaving others undefined.

10 Summary

A polymorphic function is defined using type variables in the signature. A type variable can represent an arbitrary type.
All occurences of a particular type variable appearing in a type signature must represent the same type.
An identifier will be treated as an operator symbol if it is enclosed in backquotes: "`".
An operator symbol can be treaded as an identifier by enclosing it in parenthesis: (+).

11 Homework

Define a polymorphic function dup x which returns a tuple with the argument duplicated.

Example:
$\begin{gprogram} \redtxt{? dup 1} \\ \x (1,1) \\ \\ \redtxt{? dup ''Hello, me... ... \\ \redtxt{? dup (dup 3.14)} \\ \x ((3.14,3.14), (3.14,3.14)) \end{gprogram}$

12 Homework

Define a polymorphic function copy n x which returns a list of n copies of x.

Example:
$\begin{gprogram} \redtxt{? copy 5 ''five''} \\ \x [''five'',''five'',''five'',\... ... \redtxt{? copy 5 (dup 5)} \\ \x [(5,5),(5,5),(5,5),(5,5),(5,5)] \end{gprogram}$

13 Homework

Let f be a function from Int to Int, i.e. f :: Int -> Int. Define a function total f x so that total f is the function which at value n gives the total f 0 + f 1 + + f n.

Example:
$\begin{gprogram} double x = 2*x\\ pow2 x = x\verb+^+2\\ totDub = total double\... ...\\ \redtxt{? totDub 5} \\ \x 30\\ \redtxt{? totPow 5}\\ \x 55 \end{gprogram}$

Christian S. Collberg
2005-09-16

CSc 372 - Comparative Programming Languages 10 : Haskell -- Polymorphic Functions

CSc 372 - Comparative Programming Languages
10 : Haskell -- Polymorphic Functions