[Camllist] First order compile time functorial polymorphism in Ocaml
[
Home
]
[ Index:
by date

by threads
]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
[ Message by date: previous  next ] [ Message in thread: previous  next ] [ Thread: previous  next ]
Date:   (:) 
From:  Francois Rouaix <francois@r...> 
Subject:  Re: [Camllist] First order compile time functorial polymorphism in Ocaml 
John, Sounds like Camlp4 work to me. If you haven't seen IoXML, you might want to look at it. It generates typespecific code at compiletime to support marshalling to and from XML. Copypasting and adapting to morphisms should be a simple exercise. f On Sunday, Jun 22, 2003, at 20:25 Europe/Paris, John Skaller wrote: > In ML style functional programming languages like Ocaml, > we have what is termed data polymorphism. This provides > a kind of code reuse we're all familiar with. > > However, there is another kind of polymophism > which Ocaml does not provide. Two things to consider here: > > 1. Every data structure has a map function. > 2. User defined algebraic type require a hand written map function > > It sure is inconvenient to have to remember the names > of all those map functions, not to mention having to hand > write them. Lets look at a map function: > > type 'a mylist = Empty  Cons of 'a * 'a list > > let rec map_mylist f a = match a with >  Empty > Empty >  Cons (h,t) > Cons (f h, map_mylist f t) > > It is clear from this example, that every inductive type > can have a map function generated by a purely mechanical > transformation on the type terms: that is, there > is no reason to ever write map functions again. > > The result extends easily to multiple type variables, > a map function then requires multiple function arguments. > > The result can *also* be extended to folds, iterators, > and other polymorphic algorithms (provided they're natural). > > Notation: I suggest > > polymap[t] > > denoted the map for an algebraic type, it has arity n+1 > where n is the arity of the type functor. > > Rules for generation of the map function > [brain dead nontail recursive version] > > 1. We write let rec (mapname) (argumentlist) = function > > 2. If the type is a tuple, the result is a tuple of > mapped subterms (ditto for records). > > 3. If the type is a sum (either kind), the result is > a function with a list of match cases, the result > is the same constructor with mapped arguments. > > 4. If the type is a constant, the result is that constant > > 5. If the type is a type variable, the corresponding > mapping function applied to the subterm: 'f is replaced > by f x (where x names the subterm). > > 6. If the type is a functor application (type constructor), > the result is a polymap of the functor applied to the mapped > arguments and the corresponding match term. > > 7. Handling abstract types. In order to actually summon > the above code generations, we posit a new binding construction: > > let <new_name> = polymap <type> in > > if the definition of <type> contains any opaque types, > including any abstract type of a module, primitive > not known in Pervasives, or, a class, then the client > must supply the mapping function as follows: > > let <new_name> = polymap <type> with polymap list = List.map in > etc. > > The same mechanism can be provided for folds, iterators, > etc. Because this is a first order system, we have to hand > write the functorial transformation each time. > >  > John Max Skaller, mailto:skaller@ozemail.com.au > snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia. > voice:61296600850 > > >  > To unsubscribe, mail camllistrequest@inria.fr Archives: > http://caml.inria.fr > Bug reports: http://caml.inria.fr/bin/camlbugs FAQ: > http://caml.inria.fr/FAQ/ > Beginner's list: http://groups.yahoo.com/group/ocaml_beginners > >  To unsubscribe, mail camllistrequest@inria.fr Archives: http://caml.inria.fr Bug reports: http://caml.inria.fr/bin/camlbugs FAQ: http://caml.inria.fr/FAQ/ Beginner's list: http://groups.yahoo.com/group/ocaml_beginners