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 TAA06523; Sat, 27 Jul 2002 19:32:25 +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 TAA06809 for ; Sat, 27 Jul 2002 19:32:25 +0200 (MET DST) Received: from sunny.pacific.net.au (sunny.pacific.net.au [203.25.148.40]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id g6RHWLX10729 for ; Sat, 27 Jul 2002 19:32:23 +0200 (MET DST) Received: from wisma.pacific.net.au (wisma.pacific.net.au [210.23.129.72]) by sunny.pacific.net.au with ESMTP id g6RHWHSs003619 for ; Sun, 28 Jul 2002 03:32:17 +1000 (EST) Received: from ozemail.com.au (ppp136.dyn17.pacific.net.au [61.8.17.136]) by wisma.pacific.net.au with ESMTP id DAA16248 for ; Sun, 28 Jul 2002 03:32:16 +1000 (EST) Message-ID: <3D42D920.2020800@ozemail.com.au> Date: Sun, 28 Jul 2002 03:32:16 +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: caml-list@inria.fr Subject: [Caml-list] equi-recursive Fold isomorphism Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk Given a recursive type Fix 'a . T (where 'a occurs in T) we can unfold the type to T' = T['a -> Fix 'a.T], we define unfold t = t, if t doesn't start with a fixpoint operator. Any ideas how to best implement fold, the inverse isomorphism? Brute force method: examine every subterm, and compare with the main term using equi-recusive comparison .. this seems quadratic in the number of nodes .. smarter method: only compare arguments of fixpoint binders .. can we do any better? For example, replace the subterm in the main term with a fixpoint variable, and compare the subterm with the modified main term (directly, ie. using ocaml 'compare') [I don't know how to do this 'replacement' efficiently though] -- 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