Re: List.filter in Ocaml 2.02

From: Alexey Nogin (nogin@cs.cornell.edu)
Date: Fri Mar 12 1999 - 19:41:40 MET


Date: Fri, 12 Mar 1999 13:41:40 -0500
From: Alexey Nogin <nogin@cs.cornell.edu>
To: Jean-Francois Monin <JeanFrancois.Monin@cnet.francetelecom.fr>
Subject: Re: List.filter in Ocaml 2.02

Jean-Francois Monin wrote:

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

This version has all the problems that the previous version had plus it
also allocates some memory for closure which makes things much slower
when lists are short.

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)



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