## Re: "ocaml_beginners"::[] tail recursion

Expand Messages
• ... Tail recursion is one of those things that never seems to be explained well. It s not hard, once you get it. And anything you can do with a loop you can
Message 1 of 44 , May 4, 2005
• 0 Attachment
On Thu, 5 May 2005, vly3 wrote:

> I am having trouble understanding tail recursion. I have read the
> posts about tail recursion in the archives, and I have used google to
> look up articles on tail recursion, and I still don't understand how
> to tell if a function is tail recursive or not,

Tail recursion is one of those things that never seems to be explained
well. It's not hard, once you get it. And anything you can do with a
loop you can do with tail recursion.

There are basically two rules for making a function tail recursive:

1) you can not modify the return value of the recursive call in any way-
this includes sticking the return value in into data structure, prepending
it to a list, or performing any operation on it what so ever.

2) you can not wrap the recursive call in a try/with clause to catch
exceptions.

So, some standard patterns emerge- watch for these, they'll show up
everywhere.

To work around the first limitation, a common pattern is what's called the
accumulation value. This is an extra parameter you pass into the
recursive function which accumulates the proper return value. Here's an
example of that- calculating the factorial power of a number. The naive
way would be:
let rec fact n = if (n < 2) then 1 else n * (fact (n-1));;

Unfortunately, this is not tail recursive (we'll ignore the fact that
you'll overflow integers before you hit the tail recursion for the
moment)- because we're violating the first rule, and applying an operation
(*) to the result of the recursive call. The solution is to to accumulate
the value:

let fact n =
let rec loop accum n =
if (n < 2) then
accum
else
loop (accum * n) (n-1)
in
loop 1 n
;;

The equivelent code in a procedural language, like say C, would be:
int fact(int n) {
int accum = 1;
while (n > 1) {
accum *= n;
n -= 1;
}
return accum;
}

In fact, if you look at the assembly language, the correspondence is
pretty much exact, in that both routines compile into effectively the same
object code.

Let's take another example, but this one building a list. One trick you
see a lot in building lists is that the accumulated list is built
backwards. In Ocaml, adding an element onto the head of a list is really
cheap, but adding an element to the end of a list is really expensive
(basically you have to reallocate the whole list- the longer the list, the
more expensive it is).

So what happens when we want to build a list forward, and each iteration
of the recursive function (aka the loop) we create the new last element of
the list? We use an accumulation variable, like above, except the
accumulation variable is the reverse of the list we want to create. Then,
when we're done, we just reverse the list.

An example of this is a function that creates the first N Fibinocci
numbers (I'm picking examples here that don't need a lot of extraneous
code, not for their absolute utility). So we want a function that given
the number 6, returns the list [1;1;2;3;5;8], and given 7 returns
[1;1;2;3;5;8;13]. Now first, let's just write the function that
(efficiently) calculates Fibinocci numbers:

let fib n =
let rec loop a b i = (* a is the ith fib number,
b is the i-1th fib number *)
if (i >= n) then
a
else
loop (a+b) a (i+1)
in
loop 1 1 2
;;

This is the equivelent of the Java code:

int fib(int n) {
int a = 1;
int b = 1;
for (int i = 2; i < n; ++i) {
int c = a+b;
a = c;
b = a;
}
return a;
}

But notice we don't need to instantiate the c variable explicitly in our
ocaml code (it's still there implicitly).

So now we extend the function, to handle lists. We add an accumulation
variable, which is our list, and just prepend new fib numbers as we make
them:

let fib n =
let rec loop accum a b i =
if (i >= n) then
List.rev accum
else
loop ((a+b) :: accum) (a+b) a (i+1)
in
if (n < 1) then
[]
else if (n == 1) then
[1]
else if (n == 2) then
[1;1]
else
loop [1;1] 1 1 2
;;

Now let's do something trickier. Given an input stream, let's read in all
the lines from the input stream until we hit the end of the file, and
stick all the lines in a list for processing, in order, so the first
string in the list is the first line of the file, etc. We use the
input_line function to read in the lines, which throws an End_of_file
exception if we try to read past the end of file. We play exactly the
same trick as above, and first build our list backwards, and reverse it at
the end. So our first whack at this function is:

let rec loop accum =
try
let line = input_line chan in
loop (line :: accum)
with
| End_of_file -> List.rec accum
in
loop []
;;

This is tail recursive according to rule #1 (it doesn't modify the return
value from the recursive call in any way), but falls afoul of rule- the
recursive call is inside a try/with statement. So what we do is move the
recursive call outside of try/with statement- we just set a variable if we
caught an exception. So the proper way to write this function is:

let rec loop accum =
let eof, line = (* eof is true if we caught an exception, false
otherwise *)
try
false, (input_line chan)
with
| End_of_file -> true, ""
in
if eof then
List.rev accum
else
loop (line :: accum)
in
loop []
;;

Now we're tail recursive.

Hope this helps.

Brian
• ... Yes. ... No but that is related because non-strict languages require purity to be deterministic. ... Yes. The result is a sequence of n closures, each
Message 44 of 44 , Jul 4, 2008
• 0 Attachment
On Friday 04 July 2008 06:04:45 marlenemiller71 wrote:
> Jon Harrop wrote:
> > Actually that (eta reduction, IIRC) is a dangerous practice in impure
> > languages like OCaml because it changes when the expressions are
> > evaluated.
>
> impure?

Yes.

> do you mean eager (as opposed to lazy)?

No but that is related because non-strict languages require purity to be
deterministic.

> > In this case, eta reducing by removing the "x" arguments from both sides
> > of the definition causes the function to partially evaluate sooner,
> > yielding a closure that encapsulates "n" nested function applications. If
> > you remove
>
> # let two n = 2 * n;;
>
> # let rec iter = fun n -> fun f ->
> if (n=0) then fun x->x else compose f (iter (n-1) f);;
> val iter : int -> ('a -> 'a) -> 'a -> 'a = <fun>
>
> Here, if... is evaluated and iter is applied 5 times. Right?
> # iter 5 two;;
> - : int -> int = <fun>

Yes. The result is a sequence of n closures, each calling the next and the

> # let rec iter = fun n -> fun f -> fun x ->
> if (n=0) then x else iter (n-1) f (f x);;
> val iter : int -> ('a -> 'a) -> 'a -> 'a = <fun>
>
> Whereas here, fun x... is evaluated but not if... Right?
> # iter 5 two;;
> - : int -> int = <fun>

Exactly, yes. The result is a single closure that captured "n", "f" and will
fully apply "iter" just as soon as it gets its third and final argument.

> > all arguments that were otherwise deferring the evaluation then
> > you can even
> > change the type of the expression from polymorphic to monomorphic,
> > where the
>
> Hmm! (to do: find an example)

Very easy, just partially apply any of the built-in polymorphic HOFs:

# let f = List.map List.map;;
val f : ('_a -> '_b) list -> ('_a list -> '_b list) list = <fun>

> > non-generalized type variable (e.g. '_a) will be ossified at first
> > use or even resulting in a type error if it tries to escape a compilation
> > unit.
>
> Hmm :-(

There is a trade-off between that and purity. As Haskell has shown, purity
sucks.

--
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/?e
Your message has been successfully submitted and would be delivered to recipients shortly.