Re: [Caml-list] First order compile time functorial polymorphism in Ocaml

[Francois Rouaix <francois@rouaix.org>]

John,
Sounds like Camlp4 work to me.
If you haven't seen IoXML, you might want to look at it.
It generates type-specific code at
compile-time to support marshalling to and from XML.
Copy-pasting 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 non-tail 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:61-2-9660-0850
>
>
> -------------------
> To unsubscribe, mail caml-list-request@inria.fr Archives: 
> http://caml.inria.fr
> Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: 
> http://caml.inria.fr/FAQ/
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
>
>

-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners