Re: [Caml-list] @, List.append, and tail recursion

[Olivier Andrieu <andrieu@ijm.jussieu.fr>]

 Brian Hurt [Thursday 23 January 2003] :
 > I hit a bug recently wiith @ and List.append.  Since they're recursive, 
 > not tail-recursive, on long enough lists Ocaml thinks you've gone 
 > infinitely recursive and aborts. 

 > List.append x [] ;;
 > Exits with:
 > Stack overflow during evaluation (looping recursion?).
 > 
 > So does:
 > x @ [] ;;
(not surprising, List.append 's definition is (@))

 > And it has occured to me that all of these forms *should* be
 > optimizable into loops.  The general case would work something like
 > this in C:
 > 
 > struct list_t {
 >     void * datum;
 >     struct list_t * next_p;
 > }
 > 
 > struct list_t * foo (struct list_t * x) {
 >     struct list_t * retval = NULL;
 >     struct list_t ** ptr_pp = &retval;
 > 
 >     while (x != NULL) {
 >         struct list_t * temp = alloc(sizeof(struct list_t));
 >         *ptr_pp = temp;
 >         temp->datum = expr(x->datum);
 >         temp->next_p = NULL; /* be nice to the GC */
 >         ptr_pp = &(temp->next_p);
 >         x = x->next_p;
 >     }
 >     return retval;
 > }

Well, all of this can be translated directly to caml, using the famous
Obj module. All you need is a lispish setcdr function :

,----
| let setcdr : 'a list -> 'a list -> unit = fun c v -> 
|   let c = Obj.repr c in
|   assert(Obj.is_block c) ;
|   Obj.set_field c 1 (Obj.repr v)
`----

Then one can write a tail-recursive append or a tail-recursive map :
,----
| let tr_append l1 l2 =
|   let rec proc cell = function
|     | [] ->
| 	setcdr cell l2
|     | x :: l -> 
| 	let nxt = [ x ] in
| 	setcdr cell nxt ;
| 	proc nxt l
|   in
|   match l1 with
|   | [] -> l2
|   | x :: l ->
|       let head = [ x ] in
|       proc head l ;
|       head
| 	
| let tr_map f l = 
|   let rec proc cell = function
|     | [] -> ()
|     | x :: l -> 
| 	let nxt = [ f x ] in
| 	setcdr cell nxt ;
| 	proc nxt l
|   in
|   match l with
|   | [] -> [] 
|   | x :: l ->
|       let head = [ f x ] in
|       proc head l ;
|       head
`----
This seems safe to me, as setcdr is only called on new cons cells, so
it shouldn't mess up the arguments.

Anyway, the hole abstraction thing is cleaner but needs compiler
support. 

-- 
   Olivier
-------------------
To unsubscribe, mail caml-list-request@inria.fr Archives: http://caml.inria.fr
Bug reports: http://caml.inria.fr/bin/caml-bugs FAQ: http://caml.inria.fr/FAQ/
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners