This site is updated infrequently. For up-to-date information, please visit the new OCaml website at ocaml.org.

Re: Map is not tail recursive
• David McClain
[ Home ] [ Index: by date | by threads ]
[ Search: ]

[ Message by date: previous | next ] [ Message in thread: previous | next ] [ Thread: previous | next ]
 Date: 1999-01-12 (09:45) From: David McClain Subject: Re: Map is not tail recursive
```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
>

```