Re: Map is not tail recursive

["David McClain" <dmcclain@azstarnet.com>]

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
>