November 2006 - Generics

Fwd: [Hs-Generics] Support for abstract data types
by Alexey Rodriguez 20 Dec '06

20 Dec '06

---------- Forwarded message ---------- From: Alexey Rodriguez <mrchebas(a)gmail.com> Date: Nov 14, 2006 5:46 PM Subject: Re: [Hs-Generics] Support for abstract data types To: Pablo Nogueira <pirelo(a)googlemail.com> On 11/10/06, Pablo Nogueira <pirelo(a)googlemail.com> wrote: > > Hi Alexey > > Could you please forward my replies to generics(a)haskell.org? I still > can't post and stil haven't got a reply from the administrator :-( > > One minor addition: > > > toQueue (Inl (e :*: q)) = e `prependToQueue` q > > toQueue (Inr ()) = emptyQueue > > What is `prependToQueue'? It is not a queue operation given by a queue > interface. I take it is actually "enqueue . reverse". If this is the > case, what you propose looks impractical. I assumed it to be an operation internal to the queue library, remember that the mapping is written by the Queue library writer, not the user. "prependToQueue" does not need to be exposed to the user. What is exposed is the structural representation type and the embedding projection, which the user exploits by using Queue-specialized generic functions. Cheers, Alexey

2 1

Fwd: [Hs-Generics] Support for abstract data types
by Alexey Rodriguez Yakushev 13 Nov '06

13 Nov '06

Begin forwarded message: > From: "Pablo Nogueira" <pirelo(a)googlemail.com> > Date: November 10, 2006 12:46:27 GMT+01:00 > To: "Alexey Rodriguez" <mrchebas(a)gmail.com> > Subject: Re: [Hs-Generics] Support for abstract data types > > Hi Alexey > > Could you please forward my replies to generics(a)haskell.org? I still > can't post and stil haven't got a reply from the administrator :-( > > One minor addition: > >> toQueue (Inl (e :*: q)) = e `prependToQueue` q >> toQueue (Inr ()) = emptyQueue > > What is `prependToQueue'? It is not a queue operation given by a queue > interface. I take it is actually "enqueue . reverse". If this is the > case, what you propose looks impractical.

1 0

Fwd: [Hs-Generics] Support for abstract data types
by Alexey Rodriguez Yakushev 13 Nov '06

13 Nov '06

Begin forwarded message: > From: "Pablo Nogueira" <pirelo(a)googlemail.com> > Date: November 9, 2006 18:35:58 GMT+01:00 > To: "Alexey Rodriguez" <mrchebas(a)gmail.com> > Cc: "generics(a)haskell.org" <generics(a)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(a)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 <mrchebas(a)gmail.com> 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.

1 0

patch applied (generics): LIGD tests
by Stephanie Weirich 09 Nov '06

09 Nov '06

Thu Nov 9 07:44:53 PST 2006 sweirich(a)cis.upenn.edu * LIGD tests A ./LIGD.examples/testsuite/ A ./LIGD.examples/testsuite/CompanyDatatypes.hs A ./LIGD.examples/testsuite/CompanyReps.hs A ./LIGD.examples/testsuite/LIGD.lhs A ./LIGD.examples/testsuite/Makefile A ./LIGD.examples/testsuite/bits/ A ./LIGD.examples/testsuite/bits/Main.lhs A ./LIGD.examples/testsuite/bits/Makefile A ./LIGD.examples/testsuite/bits/XBitz.hs A ./LIGD.examples/testsuite/bits/test.stdout A ./LIGD.examples/testsuite/foldTree/ A ./LIGD.examples/testsuite/foldTree/Main.hs A ./LIGD.examples/testsuite/foldTree/Makefile A ./LIGD.examples/testsuite/foldTree/test.stdout A ./LIGD.examples/testsuite/geq/ A ./LIGD.examples/testsuite/geq/Main.lhs A ./LIGD.examples/testsuite/geq/Makefile A ./LIGD.examples/testsuite/geq/test.stdout A ./LIGD.examples/testsuite/gshow/ A ./LIGD.examples/testsuite/gshow/CompanyDatatypes.hs A ./LIGD.examples/testsuite/gshow/Main.lhs A ./LIGD.examples/testsuite/gshow/Makefile A ./LIGD.examples/testsuite/gshow/test.stdout A ./LIGD.examples/testsuite/paradise/ A ./LIGD.examples/testsuite/paradise/Main.hs A ./LIGD.examples/testsuite/paradise/Makefile A ./LIGD.examples/testsuite/paradise/test.stdout

1 1

patch applied (generics): SYB1&2 tests
by Stephanie Weirich 09 Nov '06

09 Nov '06

Thu Oct 26 11:48:29 PDT 2006 sweirich(a)cis.upenn.edu * SYB1&2 tests A ./SYB1_2.examples/ A ./SYB1_2.examples/testsuite/ A ./SYB1_2.examples/testsuite/CompanyDatatypes.hs A ./SYB1_2.examples/testsuite/Makefile A ./SYB1_2.examples/testsuite/bits/ A ./SYB1_2.examples/testsuite/bits/Main.hs A ./SYB1_2.examples/testsuite/bits/Makefile A ./SYB1_2.examples/testsuite/bits/test.stdout A ./SYB1_2.examples/testsuite/foldTree/ A ./SYB1_2.examples/testsuite/foldTree/Main.hs A ./SYB1_2.examples/testsuite/foldTree/Makefile A ./SYB1_2.examples/testsuite/foldTree/test.stdout A ./SYB1_2.examples/testsuite/geq/ A ./SYB1_2.examples/testsuite/geq/Main.hs A ./SYB1_2.examples/testsuite/geq/Makefile A ./SYB1_2.examples/testsuite/geq/test.stdout A ./SYB1_2.examples/testsuite/gshow/ A ./SYB1_2.examples/testsuite/gshow/Main.hs A ./SYB1_2.examples/testsuite/gshow/Makefile A ./SYB1_2.examples/testsuite/gshow/test.stdout A ./SYB1_2.examples/testsuite/paradise/ A ./SYB1_2.examples/testsuite/paradise/Main.hs A ./SYB1_2.examples/testsuite/paradise/Makefile A ./SYB1_2.examples/testsuite/paradise/test.stdout

1 0

Support for abstract data types
by Bruno Oliveira 07 Nov '06

07 Nov '06

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".

2 1

Sample code
by oleg＠pobox.com 03 Nov '06

03 Nov '06

Hello! I wonder if we should collect some example code and make it presentable. By that I mean there should be the classification of the example, brief description, and, mainly, sample test data and the expected results. And, of course, implementations for these examples in various generic programming approaches. Incidentally, the `expressibility' section in the library description can simply enumerate which examples the library can implement. _Some_ of the examples may become the part of the benchmarking suite (at this point I'm simply interested in what is possible). Here's what I have gleaned so far, from a couple of SYB papers and the code already in DARCS: generic show: essential type is t -> String [I say essential because there may be additional arguments, say, for type representation] Description: display the term; special processing for Strings, as opposed to general arrays. Category: closed Cartesian [sorry, couldn't resist] I mean, `consumer', reduce a generic term to a value of the fixed type, String. LIGD has the implementation; no test data though. generic size: essential type t -> Int Give the size of a term (in terms of data constructors). The user should be able to assign size matrix to specific data types (like strings). Category: consumer, reduce a generic term to a value of the fixed type, Int. SYB3 example, also used in Smash. I have test data and expected results (part of syb4.hs) This example is quite similar to gshow above; I personally prefer this over gshow, because the Show class already provides the latter, so it's hard to get excited over gshow. Salary Raise: essential type t -> t Transform a term (representing an `organization' or an XML document) into the term of the same type, but with different values of some primitive fields. Ralf's dream example, from SYB1. category: type-preserving transformer Variation: uniform transformation (raise everybody's salary by 10%); or the transformation should affect only specific parts of the term. Transformation can be context-independent (increment each float field by 10%) or context- (that is, traversal history) dependent (increment each float until the money runs out). Test data can be extracted from Ralf's web site. generic minimum: essential type t Provides the 'minimal' value of any term in the universe of discourse. category: pure producer Variation: functional term may or may not be handled. LIGD example. test data can be easily extracted from it. Replace all Ints with Floats in a term: essential type t -> t' where t' = f(t). category: transformer, to a term of a different type. The output type is the function of the input type. variation: replace all Ints with Floats and negate all booleans, in a single traversal (that is, `compose' multiple compatible processing steps) Smash example; test data are available in the syb4.hs generic equality: essential type t -> t -> Bool category: binary function over two generic arguments of the same type. Variation: try essential type t -> t' -> Bool Variation: permit the user supply their own comparison procedure for some data types Variation: local extensibility [as explained in Stefan Holdermans] LIGD example (including specific comparison of integers mod 2). Need test data though. something of the type t1 -> t2 -> t3 where t3 = f(t1, t2). Generalization of zip/zipWith. I have never seen that example. Obviously a lot is missing in the above -- in particular, good names for the examples, and the test data. And the idea how to organize the files with examples and test data within our DARCS repository. Stephanie Weirich wrote: > For the latter, we talk about the ability to use the library with > types that contain > records > nested datatypes > higher-kinded types (what kinds?) > datatypes with existential components (both of kind type and > higher kinds) > datatypes with first-class polymorphic components (both of kind > type and higher kinds) > above with class constraints > GADTs (simple, and those that subsume existentials...) > datatypes with higher-kinded type arguments I'd inline this dimension into each of the above example. But we need test data... Cheers, Oleg

8 10