Date: November 9, 2006 18:35:58 GMT+01:00
Subject: Re: [Hs-Generics] Support for abstract data types
Before all, thank you for your reply. Would you send this email to the
problems posting in the past and have got no reply from the
administrator.
Just to make things clearer for me, what would the entry be for C++ STL?
STL supports generic programming on container (first-order) abstract
data types (ADTs) with iterators, where by generic I mean functions
that work for all such ADTs. You may see the iterator as the "common
representation" of ADTs used by the STL. Certainly, STL is not
designed to deal with higher-kinded ADTs. I just wanted to say that
support for ADTs should be considered as important. I'm not saying STL
is polytypic, but having a single function that works on all container
types with iterators is very generic to me, just like having generic
functions on the so-called spine view for algebraic data types is.
In the approach with generic views and the example with Queues you
give, you are basically mapping a Queue into a list, which is a left
to right iterator. The important thing is that you would have to
specify how ADTs are represented as sums of products *per* ADT, so GH
fares not better than STL in this respect, where every iterator has to
be programmed per ADT. (If iterators were generated automatically then
STL would fare really well).
At present, I believe GH supports ADTs by polytypic extension (my
suggested terminology). The generic programmer has to specify the way
an ADT is translated into sums of products. (Aside: you'll have
problems supporting constrained abstract data type such as Ord a =>
OrdSet a. You won't be able to apply gsize whose instance for * -> *
is unconstrained.)
I hope I'm not mistaken in thinking that STL is relevant in this list,
which is about generic programming, not just polytypic programming.
(Is SYB polytypic?) My point in the email is that support for abstract
data types should be taken seriously when designing a generic (or
polytypic) library, nothing more. I'm with you in that we should do
better than STL.
P.