[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:  John Skaller <skaller@o...> 
Subject:  [Camllist] First order compile time functorial polymorphism in Ocaml 
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