Map is not tail recursive

From: Juan Jose Garcia Ripoll (jjgarcia@ind-cr.uclm.es)
Date: Sun Jan 10 1999 - 11:49:53 MET


Date: Sun, 10 Jan 1999 11:49:53 +0100
From: Juan Jose Garcia Ripoll <jjgarcia@ind-cr.uclm.es>
To: Caml list <caml-list@pauillac.inria.fr>
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