The identifier list isn't really a Hope data type. It's called a type constructor and must be parameterised with an actual type before it represents one. We did this every time we declared a list ( num ) or a list ( char ). The parameter can also be a user-defined type, as with a list ( tree ) or even a type variable as in list ( alpha ), which defines a polymorphic data type. Constructing new data types like this is a compile-time operation by the way, and you shouldn't confuse it with constructing new data values, which is a run-time operation.
You can define your own polymorphic data types. Here's a version of the binary tree we defined earlier that can have any type of value in its leaves:
data tree ( alpha ) == empty ++
tip ( alpha ) ++
node ( tree ( alpha ) # tree ( alpha ) ) ;
Once again, alpha is taken to be the same type throughout one instance of a
tree. If it's a number, then all references to tree ( alpha ) are taken as
references to tree ( num ).
We can define polymorphic functions that operate on trees containing any type of object, because tree constructors are now polymorphic. Here's a function to `flatten' a binary tree into a list of the same type of object:
dec flatten : tree ( alpha ) -> list ( alpha ) ;
--- flatten ( empty ) <= nil ;
--- flatten ( tip ( x ) ) <= x :: nil ;
--- flatten ( node ( x, y ) ) <= flatten ( x ) <> flatten ( y ) ;
We can demonstrate it on various kinds of tree:
flatten( node ( tip ( 1 ), node ( tip ( 2 ), tip ( 3 ) ) ) ) ;
[ 1, 2, 3 ] : list ( num )
flatten( node ( tip ( "one" ),
node ( tip ( "two" ),
tip ( "three" ) ) ) ) ;
[ "one","two","three" ] : list ( list ( char ) )
flatten( node ( tip ( tip ( 'a' ) ),
node ( tip ( empty ),
tip ( node ( tip ( 'c' ),
empty ) ) ) ) ) ;
[ tip ( 'a' ),empty,node ( tip ( 'c' ), empty) ] : list ( tree ( char ) )
Notice how the type-checker may need to go through several levels of data
types to deduce the type of the result.