From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: weis
Received: (from weis@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id SAA07852 for caml-redistribution; Fri, 12 Mar 1999 18:07:28 +0100 (MET)
Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id LAA17942 for <caml-list@pauillac.inria.fr>; Fri, 12 Mar 1999 11:10:17 +0100 (MET)
Received: from gatesrv.RZ.UniBw-Muenchen.de (gatesrv.RZ.UniBw-Muenchen.de [137.193.11.27])
	by nez-perce.inria.fr (8.8.7/8.8.7) with ESMTP id LAA23100
	for <caml-list@inria.fr>; Fri, 12 Mar 1999 11:10:15 +0100 (MET)
Received: from auriga.informatik.unibw-muenchen.de (auriga.Informatik.UniBw-Muenchen.de [137.193.62.10]) by gatesrv.RZ.UniBw-Muenchen.de (8.8.8/8.8.Beta.1) with ESMTP id LAA16513 for <caml-list@inria.fr>; Fri, 12 Mar 1999 11:10:14 +0100 (MET)
Received: from diogenes.informatik.unibw-muenchen.de (diogenes.Informatik.UniBw-Muenchen.de [137.193.60.73])
	by auriga.informatik.unibw-muenchen.de (8.8.5/8.8.5) with SMTP id LAA21416
	for <caml-list@inria.fr>; Fri, 12 Mar 1999 11:12:39 +0100 (GMT)
Received: (qmail 6513 invoked by uid 210); 12 Mar 1999 10:10:49 -0000
Date: 12 Mar 1999 10:10:49 -0000
Message-ID: <19990312101049.6512.qmail@diogenes.informatik.unibw-muenchen.de>
From: Wolfram Kahl <kahl@diogenes.informatik.unibw-muenchen.de>
To: nogin@cs.cornell.edu
CC: Xavier.Leroy@inria.fr, caml-list@inria.fr
In-reply-to: <36E854D1.E52CD73B@CS.Cornell.EDU> (message from Alexey Nogin on
	Thu, 11 Mar 1999 18:42:09 -0500)
Subject: Re: List.filter in Ocaml 2.02
References: <19990305114112.34610@pauillac.inria.fr> <36E854D1.E52CD73B@CS.Cornell.EDU>
Sender: weis

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?