Re: List.filter in Ocaml 2.02

From: Wolfram Kahl (kahl@diogenes.informatik.unibw-muenchen.de)
Date: Fri Mar 12 1999 - 11:10:49 MET


Date: 12 Mar 1999 10:10:49 -0000
From: Wolfram Kahl <kahl@diogenes.informatik.unibw-muenchen.de>
To: nogin@cs.cornell.edu
Subject: Re: List.filter in Ocaml 2.02

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?



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