From mboxrd@z Thu Jan 1 00:00:00 1970 Received: (from majordomo@localhost) by pauillac.inria.fr (8.7.6/8.7.3) id RAA01600; Sun, 2 May 2004 17:59:36 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from concorde.inria.fr (concorde.inria.fr [192.93.2.39]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id RAA01609 for ; Sun, 2 May 2004 17:59:35 +0200 (MET DST) Received: from herd.plethora.net (herd.plethora.net [205.166.146.1]) by concorde.inria.fr (8.12.10/8.12.10) with ESMTP id i42FxXSH023919 for ; Sun, 2 May 2004 17:59:34 +0200 Received: from bhurt.plethora.net (bhurt.plethora.net [205.166.146.49]) by herd.plethora.net (8.11.6/8.10.1) with ESMTP id i42FxOR08230; Sun, 2 May 2004 10:59:25 -0500 (CDT) Date: Sun, 2 May 2004 11:04:45 -0500 (CDT) From: Brian Hurt X-X-Sender: bhurt@localhost.localdomain To: Nicolas Cannasse cc: Richard Jones , caml-list Subject: Re: [Caml-list] List.rev In-Reply-To: <004d01c42f64$731704e0$19b0e152@warp> Message-ID: MIME-Version: 1.0 Content-Type: TEXT/PLAIN; charset=US-ASCII X-Miltered: at concorde with ID 40951AE5.000 by Joe's j-chkmail (http://j-chkmail.ensmp.fr)! X-Loop: caml-list@inria.fr X-Spam: no; 0.00; caml-list:01 cannasse:01 extlib:01 newbies:01 implemented:01 alist:01 alist:01 accum:01 accum:01 nicolas:01 nicolas:01 rec:01 complexity:02 eof:02 eof:02 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Sat, 1 May 2004, Nicolas Cannasse wrote: > > Are there automatic ways to transform non-tail-recursive functions > > into tail-recursive ones? > > > > Rich. > > You can have a look at ExtLib sources. We provide tail-recursive > implementations for each List operations (with same "little o" complexity). > This is actually quite bad advice (sorry, Nicolas)- many of the "tricks" we do in Ext-Lib are not for newbies. I'm thinking specifically of the Obj.magic stuff. If you find yourself doing this anywhere else, you are almost certainly screwing up. There is a fairly standard set of tricks I use to turn non-tail-recursive functions into tail-recursive functions. The two most important ones are: 1) build lists backwards, then reverse them when they're done. For example, List.append could be implemented: let append alist blist = let revlist = List.rev_append blist (List.rev alist) in List.rev revlist ;; 2) Hoist recursive calls out of try/catch clauses, introducing variables to detect when an exception was thrown. For example, to read all the lines of a channel into a list of strings, do: let readfile chan = let rec loop accum = let eof, line = try false, (input_line chan) with | End_of_file -> true, "" in if (eof) then List.rev accum else loop (line :: accum) in loop [] ;; -- "Usenet is like a herd of performing elephants with diarrhea -- massive, difficult to redirect, awe-inspiring, entertaining, and a source of mind-boggling amounts of excrement when you least expect it." - Gene Spafford Brian ------------------- 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