[Hs-Generics] Support for abstract data types

[Bruno Oliveira]

Hello all,

Pablo Nogueira asked me to post this email in the mailing list since he 
had some problems trying to post himself. Here is the text:

I would like to propose adding the entry "support for abstract data types" (or
something related) to the template we are using for discussing generic
programming approaches.

Perhaps the entry would attract the attention of people with other definitions
of generic programming in mind, such as users of the C++ Standard Template
Library. C++ Templates are often roughly equated with a static version of
parametric polymorphism, but in the STL data types are abstract, not
algebraic. This is an important difference. 

As a start, I would propose that "support for abstract data types" could be
classified into "none", "by polytypic extension", and "generic":

1. With the term "polytypic extension" I am contributing terminology to the
   debate on whether we should use "specialisation", "instantiation", or
   "redefinition". If I'm not mistaken, "polytypic extension" is used in the
   SYB papers to refer to the possibility of providing type-specific cases for
   a polytypic function in an ad-hoc way.

2. Support for data abstraction may be achieved non-generically "by polytypic
   extension". For example, in SYB one may manually define the instance of
   Data for an abstract data type:

    instance Data a => Data (Queue a) where
	  gfoldl k z q  =  z ListToQueue `k` (QueueToList q)
	  toConstr _    =  error "toConstr"
	  dataTypeOf    =  mkNorepType "Data.Queue.Queue"
	  ...

   This is the extension of gfold. Perhaps instances like the above could be
   (or are already?) generated automatically for abstract types supporting
   some form of "toList" and "fromList" operations. Writing the above manually
   requires knowledge of the SYB implementation and would be brittle wrt to
   changes in SYB. I personally don't like it.

   Alternatively, a generic programmer may extend the polytypic function with
   a case for the abstract type using the proposed extensions of SYB3:

    instance Size a => Size (Queue a) where
      gsize = gsize . QueueToList 

   I'll talk about Generic Haskell below.

3. Support for data abstraction is "generic" if generic programmers can write
   a single generic function definition for all (or many) abstract types. This
   is better than providing definitions *for each* abstract type. I hope you
   agree with me that the latter is not *generic* programming. I believe none
   of the existing generic programming approaches support this. Perhaps it is
   time to think about it when designing a generic library.

In Generic Haskell, support for abstract types is more complicated because,
unlike SYB, the language is designed to deal with types of arbitrary
kind. Just to pinpoint a particular problem, there is a lack of
parametrisation on type-class constraints. There follows some *pseudocode*
examples to illustrate the point.

Type-specific instances of generic functions would seem easy to define:

  gsize<Queue> :: Queue a -> Int
  gsize<Queue> = gsize<List> . QueueToList

  gsize<OrdSet> :: Ord a => OrdSet a -> Int
  gsize<OrdSet> = gsize<List> . OrdSetToList

but a more generic version for types t::*->* equipped with a, say, overloaded
"toList" operation would have to be parametric on the constraint "c", which
might be "empty":

  gsize<t::*->*> :: c a => t a -> Int
  gsize<t> = gsize<List> . toList


To conclude this long email, I think data abstraction should be considered
from the start in the design of a generic programming library. On the one
hand, this should force us to see the internal representation of types as (1)
a parameter (cause we want to be generic), and (2) as something more abstract
than an encoding of the *implementation* of the type. On the other hand,
perhaps polytypic programming can then be conveyed to an object-oriented
setting without using naive encodings of algebraic data types as the
"objects".