Loading ...
Sorry, an error occurred while loading the content.

Re: "ocaml_beginners"::[] tail recursion

Expand Messages
  • Brian Hurt
    ... 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 readall chan =
      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 readall chan =
      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
    • Jon Harrop
      ... 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
        last calling your identity function.

        > # 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.