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 IAA22808; Sun, 31 Aug 2003 08:33:55 +0200 (MET DST) X-Authentication-Warning: pauillac.inria.fr: majordomo set sender to owner-caml-list@pauillac.inria.fr using -f Received: from nez-perce.inria.fr (nez-perce.inria.fr [192.93.2.78]) by pauillac.inria.fr (8.7.6/8.7.3) with ESMTP id IAA19274 for ; Sun, 31 Aug 2003 08:33:53 +0200 (MET DST) Received: from mz1.forethought.net (mzpi3.forethought.net [216.241.36.12]) by nez-perce.inria.fr (8.11.1/8.11.1) with ESMTP id h7V6XqT24991 for ; Sun, 31 Aug 2003 08:33:52 +0200 (MET DST) Received: from [216.241.35.41] (helo=swordfish) by mz1.forethought.net with esmtp (Exim 4.14) id 19tLmY-0006nr-UE for caml-list@pauillac.inria.fr; Sun, 31 Aug 2003 00:33:51 -0600 Received: from matt by swordfish with local (Exim 3.35 #1 (Debian)) id 19tLmJ-0000xj-00 for ; Sun, 31 Aug 2003 00:33:35 -0600 Date: Sun, 31 Aug 2003 00:33:35 -0600 From: Matt Gushee To: caml-list@pauillac.inria.fr Subject: Re: [Caml-list] beginner question about tail recursion Message-ID: <20030831063334.GA3405@swordfish> Reply-To: Matt Gushee Mail-Followup-To: caml-list@pauillac.inria.fr References: Mime-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.3.27i X-Loop: caml-list@inria.fr X-Spam: no; 0.00; gushee:01 gushee:01 caml-list:01 recursion:01 inspecting:01 introductory:99 unmodified:01 beginners:01 introductory:99 avoided:01 recursion:01 englewood:01 manure:01 mgushee:01 havenrock:01 Sender: owner-caml-list@pauillac.inria.fr Precedence: bulk On Sat, Aug 30, 2003 at 03:52:04PM -0700, Ram Bhamidipaty wrote: > Hi I am just getting started with OCaml. My understanding is > that it is desirable to write function in a tail recursive style. Well, I'm just getting started with *explaining* OCaml, so don't be surprised if I get it wrong. But here's how I understand it: > Can the OCaml system tell me if a function is tail recursive? I don't think so. But it's pretty easy to tell by inspecting the code, once you get used to it. There are two basic rules you need to keep in mind: 1. The recursive call must be the very last thing that happens in the function. Another way of saying this is that the function must directly return the result of the recursive call to itself, with absolutely no modification. 2. The recursive call can't be within a 'try' block. Unfortunately, this means that the most intuitive pattern for many functions (which is also the pattern found in many introductory examples) is not tail recursive. [ The following is mostly stolen from a previous post by Brian Hurt --thanks, Brian ] A common example of the problem is a function that reads from an input channel and returns all the lines as a list. The most obvious way to write this function is: 1 let rec readlines chnl = 2 try 3 let line = input_line chnl in 4 line :: (readlines chnl) 5 with End_of_file -> [] This actually breaks both of the two rules. Rule #1 is broken in line 4, because the cons operation ('::') is applied to the result of the recursive call. And of course it is within a 'try' block. A tail-recursive way to write the function would be: let rec readlines chnl lines = let line, eof = try let ln = input_line chnl in ln, false with End_of_file -> [], true in if eof then lines (* result returned unmodified *) else readlines chnl (line :: lines) (* 'line :: lines' is evaluated before applying 'readlines' *) Note the use of an accumulator (the 'lines' parameter). This is something you often need for a tail-recursive function. ** Note to OCaml documentors ** Isn't it confusing to beginners that non-tail-recursive examples are so common in introductory documentation? I would suggest adding warnings along the lines of "The above example illustrates the simplest way to write a recursive function; this is not the most efficient form, and should be avoided in performance-critical code. For more information see the discussion of tail recursion in Chapter XX." -- Matt Gushee When a nation follows the Way, Englewood, Colorado, USA Horses bear manure through mgushee@havenrock.com its fields; http://www.havenrock.com/ When a nation ignores the Way, Horses bear soldiers through its streets. --Lao Tzu (Peter Merel, trans.) ------------------- 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