> 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

-- 
Jean-Francois Monin, CNET DTL/MSV,          Tel +33 2 96 05 26 79
2 av. Pierre Marzin, 22307 Lannion, France  Fax +33 2 96 05 39 45
SANS TRAIT D'UNION :     JeanFrancois.Monin@cnet.francetelecom.fr