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 FAA12772; Mon, 23 Jun 2003 05:52:27 +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 FAA12564 for ; Mon, 23 Jun 2003 05:52:25 +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 h5N3qOT12040 for ; Mon, 23 Jun 2003 05:52:24 +0200 (MET DST) Received: from ozemail.com.au (203-213-82-73-syd-ts14-2600.tpgi.com.au [203.213.82.73]) (authenticated (0 bits)) by mail3.tpgi.com.au (8.11.6/8.11.6) with ESMTP id h5N3qE209100; Mon, 23 Jun 2003 13:52:15 +1000 Message-ID: <3EF6796E.20004@ozemail.com.au> Date: Mon, 23 Jun 2003 13:52:14 +1000 From: John Max 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: Michal Moskal CC: caml-list@inria.fr Subject: Re: [Caml-list] First order compile time functorial polymorphism in Ocaml References: <3EF5F48E.6010209@ozemail.com.au> <20030622190353.GA9806@roke.freak> Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit X-Spam: no; 0.00; ozemail:01 caml-list:01 functorial:01 michal:01 moskal:01 polynomial:01 foo:01 generalise:01 marginally:01 ctor:01 recursion:01 toxteth:01 glebe:01 2037,:01 9660:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Michal Moskal wrote: > On Mon, Jun 23, 2003 at 04:25:18AM +1000, John Skaller wrote: > First thing to consider: map function of this kind only exists for types, > where type variables occur only positively. What does that mean? > Even then, for inductive > types it requires proof (it isn't as simple as it first seems). The proof has been constructed for all polynomial types, i.e. types using only sums and products. [Paper:Functorial ML, Author:Barry Jaye, the mechanism there generalises over 'arbitrary' algorithms: I'm not proposing that, rather that the theory can be applied to hand write the generators for popular functions like map and fold] > For example consider: > > type 'a t = Foo 'a -> unit > > To map : 'a t -> 'b t here, you need f : 'b -> 'a. Ah, ok, exponential is contravariant. Probably have to think about 'a ref too. > What about t1 -> t2? (this is the real problem). And perhaps more generally, 'a t where t is contravariant? > Automatic definition of iterators and recursors for types also isn't > that simple, it requires good dose of theory. Sure. So: either add a restriction to avoid contravariance, or generalise my proposal. I have an actual problem, a large amount of my code is involved in mapping large variants. Sometimes the map is combined with some folding and other rewriting. Every time I add a new feature I have to write the map out again by hand. Every time I add a new term, I have to change all the maps to cope. The syntax for defining terms is inconveniently different to that required in a match, making cut and paste only marginally useful: Ctor of xyz ==> Ctor (xyz) -> a * b ==> (a,b) -> There's got to be a better way. Particularly, I do multiple re-mappings of a term structure, one for each feature. Then, I can see I can merge some of them into one map. Or worse, the other way around: I have a single recursion doing two jobs and find I need to unravel them. It would be good to separate out the functorial part of the operation and just write my mapping function for the cases that are special, and also to be able to interwine them into a single mapping. None of my data structures contain functions. -- 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