Re: List.filter in Ocaml 2.02

From: Jean-Francois Monin (JeanFrancois.Monin@cnet.francetelecom.fr)
Date: Fri Mar 12 1999 - 18:01:41 MET

Date: Fri, 12 Mar 1999 18:01:41 +0100
Message-Id: <199903121701.SAA28177@lsun565.lannion.cnet.fr>
From: Jean-Francois Monin <JeanFrancois.Monin@cnet.francetelecom.fr>
To: Alexey Nogin <nogin@cs.cornell.edu>
Subject: Re: List.filter in Ocaml 2.02
In-Reply-To: <36E854D1.E52CD73B@CS.Cornell.EDU>
        <36E854D1.E52CD73B@CS.Cornell.EDU>

> 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

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