Re: [Caml-list] beginner question about tail recursion

[Matt Gushee <matt@gushee.net>]

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