Wishlist: parameterizable types

This may be ambitious, but it'd be neat if PostgreSQL supported
parameterizable types. For example, suppose a contrib module defines
a "pair" type. It could be used as follows:

CREATE TABLE my_table (
coord pair(float, float)
);

The "pair" module could define functions like these for constructing
and examining pairs:

create function pair_create(a, b) returns pair(a, b);
create function pair_fst(pair(a, b)) returns a;
create function pair_snd(pair(a, b)) returns b;

Here, each function is polymorphic in two type variables, a and b. As
far as I know, PostgreSQL only supports one type variable per
function, via the anyelement keyword. Thus, unless we restrict
ourselves to only one type parameter, parameterizable types wouldn't
be very useful without support for multiple type variables.

PostgreSQL already has a parameterizable type: array. However, it
would be nontrivial to introduce another such type. Currently, nearly
every type in PostgreSQL has a corresponding array type. For example,
in pg_hba, there's money, and there's _money (array of money values).
Continuing with this pattern means we would need something like P*T
entries in pg_hba, where P is the number of type constructors (e.g.
array), and T is the number of base types.

Moreover, the array type isn't truly nestable. For one, PostgreSQL
considers int[] and int[][][][] as the same type:

> select '{1,2,3}' :: int[][][][];
int4
---------
{1,2,3}
(1 row)

Also, arrays inside of arrays aren't allowed, only multidimensional arrays:

> select '{{1,2},{3}}' :: int[][];
ERROR: multidimensional arrays must have array expressions with
matching dimensions
LINE 1: select '{{1,2},{3}}' :: int[][];

Suppose I didn't like these restrictions on the array type, and wanted
to make a type called "vector" that addresses them. It might be used
as follows:

> select '{{1,2},{3}}' :: vector(vector(int));

Note that I'm stacking the 'vector' type constructor. The array type
doesn't let you do that.

We could stretch the idea even further, and allow parameters and
recursion in user-defined types:

create type object(a) as (
key text,
value either(a, object(a))
);

C++ supports parameterizable types through templates. Java and C#
support them through generics.

What I have in mind comes from Haskell's type system (which inspired
generics in Java). The functions defined earlier could be implemented
in Haskell as:

data Pair a b = Pair a b

pair_fst :: Pair a b -> a
pair_fst (Pair a _) = a

pair_snd :: Pair a b -> b
pair_snd (Pair _ b) = b

What I'm wondering is: how complex would it be to add such a feature
to PostgreSQL's type system?

- Joey