From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id OAA23638 for caml-redistribution; Mon, 15 Mar 1999 14:30:48 +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 TAA04912 for ; Fri, 12 Mar 1999 19:41:44 +0100 (MET) Received: from simon.cs.cornell.edu (SIMON.CS.CORNELL.EDU [128.84.154.10]) by nez-perce.inria.fr (8.8.7/8.8.7) with ESMTP id TAA04455 for ; Fri, 12 Mar 1999 19:41:42 +0100 (MET) Received: from cloyd.cs.cornell.edu (CLOYD.CS.CORNELL.EDU [128.84.227.15]) by simon.cs.cornell.edu (8.9.3/8.9.3/R-2.1) with ESMTP id NAA01021; Fri, 12 Mar 1999 13:41:42 -0500 (EST) Received: from CS.Cornell.EDU (nogin@GULAG.CS.CORNELL.EDU [128.84.248.53]) by cloyd.cs.cornell.edu (8.8.8/8.8.8/M-1.12) with ESMTP id NAA19752; Fri, 12 Mar 1999 13:41:41 -0500 (EST) Sender: weis Message-ID: <36E95FE4.BB78EF8E@CS.Cornell.EDU> Date: Fri, 12 Mar 1999 13:41:40 -0500 From: Alexey Nogin Organization: Cornell University, department of Computer Science X-Mailer: Mozilla 4.08 [en] (X11; U; Linux 2.0.37 i686) MIME-Version: 1.0 To: Jean-Francois Monin CC: caml-list@inria.fr Subject: Re: List.filter in Ocaml 2.02 References: <19990305114112.34610@pauillac.inria.fr> <36E854D1.E52CD73B@CS.Cornell.EDU> <199903121701.SAA28177@lsun565.lannion.cnet.fr> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Jean-Francois Monin wrote: > > 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 This version has all the problems that the previous version had plus it also allocates some memory for closure which makes things much slower when lists are short. Alexey -------------------------------------------------------------- Home Page: http://www.cs.cornell.edu/nogin/ E-Mail: nogin@cs.cornell.edu (office), ayn2@cornell.edu (home) Office: Upson 4139, tel: 1-607-255-4934 ICQ #: 24708107 (office), 24678341 (home)