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 KAA18151 for caml-redistribution; Tue, 12 Jan 1999 10:45:02 +0100 (MET)
Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id TAA31167 for <caml-list@pauillac.inria.fr>; Mon, 11 Jan 1999 19:51:37 +0100 (MET)
Received: from cepheus.azstarnet.com (cepheus.azstarnet.com [169.197.56.195])
	by concorde.inria.fr (8.8.7/8.8.7) with ESMTP id TAA26861
	for <caml-list@pauillac.inria.fr>; Mon, 11 Jan 1999 19:51:36 +0100 (MET)
Received: from dylan (dialup18ip105.tus.azstarnet.com [169.197.38.233])
	by cepheus.azstarnet.com (8.9.1a/8.9.1a) with SMTP id LAA29375;
	Mon, 11 Jan 1999 11:48:20 -0700 (MST)
X-Sent-via: StarNet http://www.azstarnet.com/
Message-ID: <001101be3d93$66516610$210148bf@dylan>
From: "David McClain" <dmcclain@azstarnet.com>
To: "Juan Jose Garcia Ripoll" <jjgarcia@ind-cr.uclm.es>,
        "Caml list" <caml-list@pauillac.inria.fr>
Subject: Re: Map is not tail recursive
Date: Mon, 11 Jan 1999 11:51:25 -0700
MIME-Version: 1.0
Content-Type: text/plain;
	charset="iso-8859-1"
Content-Transfer-Encoding: 7bit
X-Priority: 3
X-MSMail-Priority: Normal
X-Mailer: Microsoft Outlook Express 4.72.3110.5
X-MimeOLE: Produced By Microsoft MimeOLE V4.72.3110.3
Sender: weis

Juan got me thinking about this problem... So here is a solution:

external rplacd : 'a list -> 'a list -> unit = "rplacd"

let list_map fn lst =
  (* A properly tail recursive definition of Map *)
  match lst with
      [] -> []  (* OCAML represents [] specially - can't rplacd *)
    | h :: t ->
         let rslt = [fn h] in
         let rec iter lst tail =
            match lst with
               [] -> rslt
             | h :: t ->
                  let elt = [fn h] in
                  rplacd tail elt;
                  iter t elt
         in
           iter t rslt

-- and the external C code is

value rplacd(value cell, value item)
{
  Store_field(cell,1,item);
  return Val_unit;
}



-----Original Message-----
From: Juan Jose Garcia Ripoll <jjgarcia@ind-cr.uclm.es>
To: Caml list <caml-list@pauillac.inria.fr>
Date: Monday, January 11, 1999 02:26
Subject: Map is not tail recursive


>Hi,
>
>I've had a look at the List package and it seems that it is not properly
>tail recursive. Even more, for medium to large lists it exhausts the
>stack. I would suggest either recoding it as
>
>let map f a =
>   let domap f done todo =
>      match todo with
>         [] -> List.reverse done
>       | (x::xs) -> domap (f x)::done xs
>   in domap f [] a
>
>Another possibility would be to introduce destructive operations such as
>Scheme's setcdr! and setcar!. This would eliminate the need of using
>List.reverse, at the cost of introducing some imperative style.
>
>Please excuse any mistake -- I'm quite new to this language.
>
>Regards
>
> Juanjo
>