Fwd: [Hs-Generics] Support for abstract data types

Begin forwarded message:

From: "Pablo Nogueira" Date: November 9, 2006 18:35:58 GMT+01:00 To: "Alexey Rodriguez" Cc: "generics@haskell.org" Subject: Re: [Hs-Generics] Support for abstract data types

Before all, thank you for your reply. Would you send this email to the generics@haskell.org list if you don't see it arriving there? I had problems posting in the past and have got no reply from the administrator.

On 07/11/06, Alexey Rodriguez wrote:

...

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.