# 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

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