This is a multi-part message in MIME format.
--------------9FB4D0D35F15A05DBD8B1B67
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Here is a slightly corrected version of my proposal. It has a few
grammar fixes and since I am sending it as an attachment it shouldn't
have the formatting problems.
Feedback most welcome. An html, and ps version of this report is
available at http://metalab.unc.edu/kevina/ntp.
--
Kevin Atkinson
[EMAIL PROTECTED]
http://metalab.unc.edu/kevina/
--------------9FB4D0D35F15A05DBD8B1B67
Content-Type: text/plain; charset=us-ascii;
name="ntp.txt"
Content-Transfer-Encoding: 7bit
Content-Disposition: inline;
filename="ntp.txt"
Nameable Type Parameters
Kevin Atkinson
[EMAIL PROTECTED]
The Basic Problem
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 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, mainly 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 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)
-> (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 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.
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.
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 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-24
--------------9FB4D0D35F15A05DBD8B1B67--
