From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: weis Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id SAA17206 for caml-redistribution; Fri, 12 Mar 1999 18:14:19 +0100 (MET) 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 SAA19729 for ; Fri, 12 Mar 1999 18:01:45 +0100 (MET) Received: from p-biset.issy.cnet.fr (p-biset.issy.cnet.fr [139.100.0.33]) by nez-perce.inria.fr (8.8.7/8.8.7) with SMTP id SAA02079; Fri, 12 Mar 1999 18:01:43 +0100 (MET) Received: from l-mhs1.lannion.cnet.fr ([161.104.1.59]) by p-biset.issy.cnet.fr with SMTP (Microsoft Exchange Internet Mail Service Version 5.5.2232.9) id GGMKQPL6; Fri, 12 Mar 1999 17:57:50 +0100 Received: from lsun565.lannion.cnet.fr ([161.104.10.182]) by l-mhs1.lannion.cnet.fr with SMTP (Microsoft Exchange Internet Mail Service Version 5.5.2232.9) id ZNBGS5RA; Fri, 12 Mar 1999 18:06:09 +0100 Received: from lsun565.cnet by lsun565.lannion.cnet.fr (SMI-8.6/SMI-SVR4) id SAA28177; Fri, 12 Mar 1999 18:01:41 +0100 Date: Fri, 12 Mar 1999 18:01:41 +0100 Message-Id: <199903121701.SAA28177@lsun565.lannion.cnet.fr> From: Jean-Francois Monin MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit To: Alexey Nogin Cc: Xavier Leroy , caml-list@inria.fr Subject: Re: List.filter in Ocaml 2.02 In-Reply-To: <36E854D1.E52CD73B@CS.Cornell.EDU> References: <19990305114112.34610@pauillac.inria.fr> <36E854D1.E52CD73B@CS.Cornell.EDU> X-Mailer: VM 6.37 under Emacs 20.2.1 Sender: weis > let rec filter f = function > [] -> [] > | (h::t) as l -> > if f h then > let rem = filter f t in > if rem == t then l else h::rem > else > filter f t Here is a version without "==" and "as", with the same property on memory allocation. Pierre Weis told me that the trick (called "sharing transducers") is due to G. Huet and was already present in Caml V3.1 pervasives more than ten years ago. exception Identity let share f x = try f x with Identity -> x let filter f l = let rec fil = function | [] -> raise Identity | h :: t -> if f h then h :: fil t else share fil t in share fil l -- Jean-Francois Monin, CNET DTL/MSV, Tel +33 2 96 05 26 79 2 av. Pierre Marzin, 22307 Lannion, France Fax +33 2 96 05 39 45 SANS TRAIT D'UNION : JeanFrancois.Monin@cnet.francetelecom.fr