List.filter in Ocaml 2.02

From: Alexey Nogin (nogin@cs.cornell.edu)
Date: Fri Mar 12 1999 - 00:42:09 MET


Date: Thu, 11 Mar 1999 18:42:09 -0500
From: Alexey Nogin <nogin@cs.cornell.edu>
To: Xavier Leroy <Xavier.Leroy@inria.fr>
Subject: List.filter in Ocaml 2.02

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)



This archive was generated by hypermail 2b29 : Sun Jan 02 2000 - 11:58:20 MET