Nameable Type Parameters
Kevin Atkinson
[EMAIL PROTECTED]
The Basic Problem
The basic problem with Haskell type system that it is impossible to
make both Array and a list of tuple pairs a member of a class to
lookup elements based on an index. It is also impossible to make both
lists and arrays a member of of map class where items in the array
are
treated as an associated pair. Although in practice this may not be a
serious problem, it does put a series hinder on combing up with a
good
clean abstraction of common data structures and algorithms in
Haskell.
It is probably also one of the reasons Haskell received a B while Ada
received an A in support for reuse in a controlled experiment to
judge
the effectiveness of several different language for prototyping
support.1
One solution within Haskell is to use vague classes:
class Find c i e where
find :: i -> c -> e
class Map a b c d where
map :: (a -> b) -> c -> d
instance Eq i => Find [(i,e)] i e where ...
instance Map a b [a] [b] where ...
instance Find (Array i e) i e ...
instance Map (i,e) (j, f) (Array i e) (Array j f) where...
However this solution has several problems:
1.
When used with a function like show it will lead to an
unresolved overloading because Haskell can't figure out the
return type.
2.
The instance declaration are unnecessary ugly.
3.
The map functions does not promise to return a container of
the
same type based on the class declaration.
Another solution within current Haskell is to make a new data type:
data MyArray c (i,e) = MyArray c
myarray :: Array i e -> MyArray (Array i e) (i,e)
myarray a = MyArray a
which will solve the problem of vague classes but will introduce a
new
problem, manly that writing the Map class such as
class Map c a b where
map :: (a -> b) -> c a -> c b
will not allow a map to be defined over a MyArray where the element
types are not the same as the container type will also change.
Defining the map instance for Array like so
instance Map MyArray (Array i e) (i,e) (j,f) where ...
will force j and f to be the same type of i and e respectfully. In
order allow the contents type to change the map function will have to
have a signature of
map :: ((i,e) -> (j,f)) -> (MyArray (Array i e)) (i,e)
-> (MyArray (Array j f)) (i,e)
which is not allowed as (MyArray (Array i e)) is the container type
and it changed when the content types changed. Thus the map function
will have to have have to have a vague signature such as in the
original example. This defeats the whole purpose of defining a new
type. Defining a new type also is not transparent to the end user
which defeats the whole purpose of coming up with an abstraction.
Nameable Type Parameters
Nameable type parameters is simply a way to attach labels to existing
types. These labels can then be used to resolve overloading in a much
more flexible way than Haskell currently can.
To attach the a label to a type simple define it using the syntax
assign ::= label atype = atype'
label ::= valid uppercase Haskell identifier
atype ::= valid Haskell type
atype' ::= atype
For example the Array class can have an Inx, El, and Con type label
attached to it with the commands:
Inx Array i e = i
El Array i e = e
Con Array i e = (i,e)
Multiple assign statements may be given for the same label. A type
label is then used by extending the valid Haskell type syntax to:
type ::= simple-type label-type
simple-type ::= [single-type ]+
label-type :: = [label: type']+
single-type ::= type-name | type-var
type-name ::= valid uppercase Haskell identifier
type-var ::= valid lowercase Haskell identifier
type' ::= type
(Function, List and Tuple types will also work however for the
purpose
of this explanation, they will be ignored as it should be easy to
expand the grammar to support them.)
If the kind of simple-type is * then look for an assign with a
matching label, and a matching atype and bind type' to atype' if it
can. If it can't it will keep searching. If the kind of simple-type
is
* -> * than look for either an assign with the same label in which
the
atype has a kind of * -> * or has at least two single-types. If the
atype has two single-types drop the last single-type when trying to
find a match. Once a match is found, complete the type by applying
the
dropped type and try to bind type' to atype' if it can. If it can't
keep searching. Do a similar thing if the kind is * -> * -> * but
drop
the last two single-types. Etc...
For example the type el in ``Array El:el'' will match the assign
statement ``El Array i e = e'' because the kind of Array is * -> * ->
* and the assignment statement has at least three single-types. The
type-var el will then be assigned the type for the last parameter of
Array. So the statement ``Array E:el'' is really like saying ``Array
_
el''. Multiple type labels may also be specified. The type ``Array
El:el Inx:el'' would just be another way to write ``Array ix el.''
The
beauty of the nameable type parameters system is that it can
represent
types which can not normally be expressed Haskell such as ``Array
Con:c''.
Atype and possibly atype' should also be allowed to have type labels
in it, however I have not worked out the details of how it would
work.
The Solution with Nameable Type Parameters
Using Nameable Type Parameters the problem presented in section 1 can
easily be solved.
class Find c i e where
find :: i -> c Inx:i El:e -> e
class Map c a b where
map :: (a -> b) -> c Con:a -> c Con:b
Con [a] = a
Inx [(i,e)] = i
El [(i,e)] = e
Con Array i e = (i,e)
Inx Array i e = i
El Array i e = e
instance Eq i => Find [] i e where ...
instance Map [] a b where ...
instance Find Array i e ...
instance Map Array (i,e) (j,k) where ...
And it has none of the drawbacks that the solution in section 1 has.
Conclusion
I believe that nameable type parameters provide an very elegant
solution to a very nasty limitation in Haskell. Please let me know
what you think by emailing me at [EMAIL PROTECTED] or sending email
the Haskell mailing list at [EMAIL PROTECTED] An html, text, TeX,
dvi, ps, and LyX version of this document is available at
http://metalab.unc.edu/kevina/ntp/.
_________________________________________________________________
Footnotes
... support.1
Paul Hudak & Mark P. Jones, Haskell vs. Ada vs.C++ vs. Awk vs.
... An Experiment in Software Prototyping Productivity, July
4,
1994
_________________________________________________________________
1999-05-22
--
Kevin Atkinson
[EMAIL PROTECTED]
http://metalab.unc.edu/kevina/
