Version française
Home     About     Download     Resources     Contact us    

This site is updated infrequently. For up-to-date information, please visit the new OCaml website at

Browse thread
[Caml-list] First order compile time functorial polymorphism in Ocaml
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: 2003-06-23 (08:07)
From: Francois Rouaix <francois@r...>
Subject: Re: [Caml-list] First order compile time functorial polymorphism in Ocaml
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.


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 = 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,
> snail:10/1 Toxteth Rd, Glebe, NSW 2037, Australia.
> voice:61-2-9660-0850
> -------------------
> To unsubscribe, mail Archives: 
> Bug reports: FAQ: 
> Beginner's list:

To unsubscribe, mail Archives:
Bug reports: FAQ:
Beginner's list: