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 IAA15017 for caml-redistribution; Fri, 12 Mar 1999 08:48:00 +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 AAA21978 for ; Fri, 12 Mar 1999 00:42:14 +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 AAA06733; Fri, 12 Mar 1999 00:42:12 +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 SAA16800; Thu, 11 Mar 1999 18:42:11 -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 SAA13708; Thu, 11 Mar 1999 18:42:10 -0500 (EST) Sender: weis Message-ID: <36E854D1.E52CD73B@CS.Cornell.EDU> Date: Thu, 11 Mar 1999 18:42:09 -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: Xavier Leroy CC: caml-list@inria.fr Subject: List.filter in Ocaml 2.02 References: <19990305114112.34610@pauillac.inria.fr> Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Hi, The filter function implementation does not seem to be too efficient. I did some testing once and it turned out that the most efficient (for my applications) way to write the filter function was: 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 The main gain here is that we do not allocate any new memory for sublist (or the whole list) that does not change as a result of the filtering. 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)