Re: List.filter in Ocaml 2.02

[Wolfram Kahl <kahl@diogenes.informatik.unibw-muenchen.de>]

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?

Being curious...


Wolfram




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

Will filter be expanded for short constant lists at compile time in
any way?
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?