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 DAA08148; Tue, 24 Jun 2003 03:00:43 +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 DAA08462 for ; Tue, 24 Jun 2003 03:00:41 +0200 (MET DST) Received: from kurims.kurims.kyoto-u.ac.jp (kurims.kurims.kyoto-u.ac.jp [130.54.16.1]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id h5O10dX05945 for ; Tue, 24 Jun 2003 03:00:39 +0200 (MET DST) Received: from localhost (suiren.kurims.kyoto-u.ac.jp [130.54.16.25]) by kurims.kurims.kyoto-u.ac.jp (8.9.3p2/3.7W) with ESMTP id KAA13046; Tue, 24 Jun 2003 10:00:35 +0900 (JST) To: carette@mcmaster.ca Cc: caml-list@inria.fr Subject: Re: [Caml-list] First order compile time functorial polymorphism in Ocaml In-Reply-To: References: <3EF5F48E.6010209@ozemail.com.au> X-Mailer: Mew version 1.94.2 on Emacs 21.2 / Mule 5.0 (SAKAKI) Mime-Version: 1.0 Content-Type: Text/Plain; charset=us-ascii Content-Transfer-Encoding: 7bit Message-Id: <20030624100034Q.garrigue@kurims.kyoto-u.ac.jp> Date: Tue, 24 Jun 2003 10:00:34 +0900 From: Jacques Garrigue X-Dispatcher: imput version 20000228(IM140) X-Spam: no; 0.00; jacques:01 caml-list:01 functorial:01 reuse:01 haskell:01 datatype:01 recursion:01 fixpoints:01 generic:01 mor:99 params:01 iin:99 wwwfun:01 ocaml:01 closure:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk From: "Jacques Carette" > I most certainly would welcome such a set of tools for reuse. > > Has anyone seriously looked (from an ML point of view) at the "scrap > your boilerplate" paper from the Haskell crowd ? > > When faced with the following issue myself for a 'monster' algebraic > datatype (but containing no negatives), I wrote the code found > below. I would welcome any and all criticisms of it [the code works > and is useful, but is doubtless a horrible hack]. > > Jacques My standard way to approach such problems is to use open recursion: I find it simpler and more general. Yet you have to understand fixpoints to use it properly. let map_one f = function | Msum x -> Msum (List.map f x) | Mprod x -> Mprod (List.map f x) | Mpow(x,y) -> Mpow (f x, fy) ... | Mstateseq x -> Mstateseq (List.map f x) | Mint _ | Mbool _ | Mfloat _ | Mstring _ | Mlocal _ | Mexport _ | Mparam _ as x -> x Then you can derive all other mapping functions easily. let rec generic_traverse filter f x = let z = map_one (generic_traverse filter f) x in if filter z then f z else z let rec deep_map f x = f (map_one f x) etc... Or you can use it directly let rec flatten x = match map_one flatten x with | Mlist x -> List.map Simpl.flatten x | Mseq x -> List.map Simpl.flatten2 x | x -> x Jacques (aussi) Your original code: > (* part of a toy interpreted for a Maple-like language *) > open Maple;; > > let rec generic_traverse filter f x = > let traverse r = generic_traverse filter f r in > let activate z = if filter z then f z else z in > let tt = function > | Mint x as z -> activate z > | Mbool x as z -> activate z > | Mfloat(x,y) as z -> activate z > | Mname x as z -> activate z > | Mstring x as z -> activate z > | Mlocal x as z -> activate z > | Mexport x as z -> activate z > | Mparam x as z -> activate z > | Msum x -> activate(Msum (List.map traverse x)) > | Mprod x -> activate(Mprod (List.map traverse x)) > | Mpow(x,y) -> activate(Mpow(traverse x, traverse y)) > | Mcomp(o,x,y) -> activate(Mcomp(o, traverse x, traverse y)) > | Mtableref(n,i) -> activate(Mtableref( traverse n, List.map traverse i)) > | Mnot x -> activate(Mnot(traverse x)) > | Mand(x,y) -> activate(Mand(traverse x, traverse y)) > | Mor(x,y) -> activate(Mor(traverse x, traverse y)) > | Mxor(x,y) -> activate(Mxor(traverse x, traverse y)) > | Mimplies(x,y) -> activate(Mimplies(traverse x, traverse y)) > | Mrange(x,y) -> activate(Mrange(traverse x, traverse y)) > | Mproc x -> > let f = function > | None -> None > | Some z -> Some(traverse z) in > let y=f x.mresult_type in > activate(Mproc( { > mparams = List.map traverse x.mparams; > mresult_type = y; > mlocals = List.map traverse x.mlocals; > mclosure = x.mclosure; (* do not traverse the closure! *) > moptions = List.map traverse x.moptions; > mdescription = List.map traverse x.mdescription; > mbody = List.map traverse x.mbody > } )) > | Mmodule x -> activate(Mmodule( { > mmod_params = List.map traverse x.mmod_params; > mmod_locals = List.map traverse x.mmod_locals; > mmod_exports = List.map traverse x.mmod_exports; > mmod_closure = x.mmod_closure; (* do not traverse the closure! *) > mmod_options = List.map traverse x.mmod_options; > mmod_description = List.map traverse x.mmod_description; > mbody_of_module = List.map traverse x.mbody_of_module > } )) > | Mfunc(n,i) -> activate(Mfunc( traverse n, List.map traverse i)) > | Mforfrom(i,ifrom,ito,iby,iwhile,body) -> > activate(Mforfrom(traverse i, traverse ifrom, traverse ito, > traverse iby, traverse iwhile, List.map traverse body)) > | Mforin(i,iin,iwhile,body) -> > activate(Mforin(traverse i, traverse iin, traverse iwhile, > List.map traverse body)) > | Mreturn x -> activate(Mreturn(traverse x)) > | Merror x -> activate(Merror(traverse x)) > | Mread x -> activate(Mread(traverse x)) > | Muneval x -> activate(Muneval(traverse x)) > | Msave x -> activate(Msave(List.map traverse x)) > | Mdcolon(x,y) -> activate(Mdcolon(traverse x, traverse y)) > | Massign(x,y) -> activate(Massign(List.map traverse x, List.map traverse y)) > | Mseq x -> activate(Mseq(List.map traverse x)) > | Mlist x -> activate(Mlist(List.map traverse x)) > | Mif (x,y,z) -> activate(Mif( (traverse x), (traverse y), (traverse z) )) > | Mstatseq x -> activate(Mstatseq(List.map traverse x)) > (*| _ as x -> activate x *) > in > tt x > ;; > > (* example [fake] use *) > > let filt = function > | Mlist _ | Mseq _ -> true > | _ -> false > and > do_something = function > | Mlist x -> List.map Simpl.flatten x > | Mseq x -> List.map Simpl.flatten2 x > | _ -> raise CannotHappenButCompilerCantKnowIt ;; --------------------------------------------------------------------------- Jacques Garrigue Kyoto University garrigue at kurims.kyoto-u.ac.jp JG ------------------- 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