PPP Exercises: Parametric polymorphism

Exercise: Lists of different types

  1. Define a type that describes a list of integer numbers. Work with functional abstract types that have been introduced in the exercise Programming Styles and Abstract Data Types. Then define functions that create a (initially empty) list of integers, insert an integer and delete specific integers (e.g. all fives) from the list, and check if a given list contains a given number. Do not use the module 'list'!
  2. The same as above with strings.
  3. The same as above with tuples that contain both a number and a string, e.g. persons with name and age.

Exercise: Lists of strings with different equality predicates

Modify the solution of the previous exercise, second part, so that the equality between strings is checked in different ways. For example, consider the case sensitivity. That means that the equality between two strings is checked usually in a case sensitive way, so strings are only considered equal if a capital (resp. small) letter in one string corresponds to a capital (resp. small) letter in the other string. Try to check the equality in a case insensitive way (see modules 'string' and 'char').
The solution should be as generic as possible. Consider to use higher order functions (i.e. functions that accept functions as parameters).

Exercise: Lists using parametric polymorphism

The advantages of parametric polymorphism are now going to become obvious as you will gather the solutions of the previous exercises into a single tuple 'list' of type 'List' that implements lists of any element type using a user-defined equality predicate. Use type operators; see exercise Type Operators. Refer to the interface 'List.ti' and it's implementation 'list.tm'. Copy this implementation and change it.

Ulrike Steffens, 1994