List.filter in Ocaml 2.02

From: Alexey Nogin (
Date: Fri Mar 12 1999 - 00:42:09 MET

Date: Thu, 11 Mar 1999 18:42:09 -0500
From: Alexey Nogin <>
To: Xavier Leroy <>
Subject: List.filter in Ocaml 2.02


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
         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.

Home Page:
E-Mail: (office), (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