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: Jean-Francois Monin <JeanFrancois.Monin@c...>
Subject: Re: List.filter in Ocaml 2.02
> 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