Kevin Atkinson
kevinatk@home.com
The basic problem with Haskell type system is 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 a 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 serious hinder on coming 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 the this problem within Haskell is to use vague classes:
class Find c i e whereHowever this solution has several problems:
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...
data MyArray c (i,e) = MyArray cwhich will solve the problem of vague classes but will introduce a new problem, mainly that writing the Map class such as
myarray :: Array i e -> MyArray (Array i e) (i,e)
myarray a = MyArray a
class Map c a b wherewill 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
map :: (a -> b) -> c a -> c b
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 to 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)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 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.
-> (MyArray (Array j f)) (j,f)
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'For example, the Array class can have an Inx, El, and Con type label attached to it with the commands:
label ::= valid uppercase Haskell identifier
atype ::= valid Haskell type
atype' ::= atype
Inx Array i e = iMultiple assign statements may be given for the same label. A type label is then used by extending the valid Haskell type syntax to:
El Array i e = e
Con Array i e = (i,e)
type ::= simple-type label-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.)
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
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.
Overlapping atypes should also be allowed as Haskell should chose the most specific type in the same manner Hugs and GHC does with overlapping instances.
Using Nameable Type Parameters the problem presented in section 1 can easily be solved.
class Find c i e whereAnd it has none of the drawbacks that the solution in section 1 has.
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 ...
I believe that nameable type parameters provide an elegant solution to a very nasty limitation in Haskell. Please let me know what you think by emailing me at kevinatk@home.com or sending email the Haskell mailing list at haskell@haskell.org. An html, text, TeX, dvi, ps, and LyX version of this document is available at http://metalab.unc.edu/kevina/ntp/.