Version française
Home     About     Download     Resources     Contact us    
Browse thread
Objective Caml 2.02
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
Date: -- (:)
From: Alexey Nogin <nogin@c...>
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)