Re: List.filter in Ocaml 2.02

[Alexey Nogin <nogin@cs.cornell.edu>]

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)