From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id UAA03079; Sun, 22 Jun 2003 20:25:38 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id UAA03411 for ; Sun, 22 Jun 2003 20:25:36 +0200 (MET DST) Received: from mail3.tpgi.com.au (mail.tpgi.com.au [203.12.160.59]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id h5MIPYT01207 for ; Sun, 22 Jun 2003 20:25:35 +0200 (MET DST) Received: from ozemail.com.au (syd-ts18-2600-174.tpgi.com.au [203.58.21.174]) (authenticated (0 bits)) by mail3.tpgi.com.au (8.11.6/8.11.6) with ESMTP id h5MIPUi20115 for ; Mon, 23 Jun 2003 04:25:30 +1000 Message-ID: <3EF5F48E.6010209@ozemail.com.au> Date: Mon, 23 Jun 2003 04:25:18 +1000 From: John Skaller User-Agent: Mozilla/5.0 (X11; U; Linux i686; en-US; rv:0.9.2.1) Gecko/20010901 X-Accept-Language: en-us MIME-Version: 1.0 To: caml-list@inria.fr Subject: [Caml-list] First order compile time functorial polymorphism in Ocaml Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Spam: no; 0.00; ozemail:01 functorial:01 reuse:01 mylist:01 functor:01 subterm:01 opaque:01 pervasives:01 toxteth:01 glebe:01 2037,:01 9660:01 0850:01 ocaml:01 rec:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk 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 = polymap in if the definition of 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 = polymap 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