Re: Map is not tail recursive

From: David McClain (dmcclain@azstarnet.com)
Date: Mon Jan 11 1999 - 19:51:25 MET


From: "David McClain" <dmcclain@azstarnet.com>
To: "Juan Jose Garcia Ripoll" <jjgarcia@ind-cr.uclm.es>,
Subject: Re: Map is not tail recursive
Date: Mon, 11 Jan 1999 11:51:25 -0700

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
>



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