Re: List.filter in Ocaml 2.02

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

Wolfram Kahl wrote:

> Alexey Nogin <nogin@cs.cornell.edu> writes:
>
>  > The filter function implementation does not seem to be too efficient.
>  > I did some testing once and it turned out that the most efficient
>  > (for my applications) way to write the filter function was:
>  >
>  > 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
>  >
>  > The main gain here is that we do not allocate any new memory for sublist
>  > (or the whole list) that does not change as a result of the filtering.
>
> The intended sharing here is not fully explicit, but partially implicit.
> If this works as described, then it should not make a difference from:
>
> let rec filter f = function
>    [] as l -> l
>    | ...
>
> , where the sharing is now fully explicit.
> The fact that this is reported to work anyway, implies
> that the compiler shares these common subexpressions ``[]'',
> and this gets me asking:
>
> How far does this kind of common subexpression sharing extend?
> Does it work for user-defined datatypes, too?
> Does it work only for zero-ary constructors, or are some
> more complicated constructions recognised, too?

As far as I understand it, for unboxed values such as integers and zero-ary
constants (such as []) in user-defined datatypes == and = are equivalent. It
has nothing to do with the fact that they are common subexpressions - if you
write let x = [] in some module and let y = [] in another, it will still be
the case that x == y.

> P.S.: Does it work for ``filter f'', or is it useful to write
>       (as I often do):
>
>  > let filter f =
>  >  let rec f1 = function
>  >     [] -> []
>  >   | (h::t) as l ->
>  >       if f h then
>  >          let rem = f1 t in
>  >          if rem == t then l else h::rem
>  >       else
>  >          f1 t
>  >  in f1

This will allocate memory for the closure which is contrary to the main goal -
not allocating anything unless really necessary and not allocate anything at
all when list does not change.

> Will filter be expanded for short constant lists at compile time in
> any way?

I do not think so.

> Or will e.g. List.fold_right or List.fold_left
> (known to be primitively recursive at compile-time of user modules :-)
> be expanded for short constant lists at compile time
> by the inlining mechanism?

As far as I know, recursive functions are never inlined.

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)