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

Re: "ocaml_beginners"::[] [OT]: tail-recursiveness

Expand Messages
  • Oliver Bandel
    Hello Ryan, ... Hmhh, because it s nit language-specific and is more an algorithmic question. [...] ... [...] ... OK, then the following is *not*
    Message 1 of 8 , Sep 3, 2002
    • 0 Attachment
      Hello Ryan,


      On Tue, 3 Sep 2002, Ryan Tarpine wrote:

      > >From: Oliver Bandel <oliver@...-berlin.de>
      > >
      > >Hello,
      >
      > Hi. Why did you call this question OT? ;)

      Hmhh, because it's nit language-specific and is more
      an algorithmic question.


      [...]
      > let rec sum n =
      > if n = 0 then 0
      > else n + (sum (n-1))
      > ;;
      >
      > Tracing an example call, we get
      > sum 3
      > 3 + (sum 2)
      > 3 + (2 + (sum 1))
      > 3 + (2 + (1 + (sum 0)))
      > 3 + (2 + (1 + 0))
      > 3 + (2 + 1)
      > 3 + 3
      > 6
      [...]
      > let rec sum n acc =
      > if n = 0 then acc
      > else (sum (n-1) (acc+n))
      > ;;
      >
      > Now instead of calling (sum n), though, you need to call (sum n 0). Tracing
      > it, we get
      > sum 3 0
      > sum 2 (0+3 = 3)
      > sum 1 (3+2 = 5)
      > sum 0 (5+1 = 6)
      > 6
      >
      > * The tail-recursive version does some work FIRST and then calls a function
      > with those results
      > * The non-tail-recursive version calls a function and then does some work
      > LATER with what that returned

      OK,

      then the following is *not* tail-recursive:


      let times n s = match n with
      0 -> ""
      | _ -> s ^ times (n-1) s


      BTW: does it mke a differnece (in any respect, maybe ocaml-specific?)
      to write it in this way:


      let times n s = match n with
      0 -> ""
      | _ -> times (n-1) s ^ s



      And how could a tail-recursive version look like?

      And: Is there a mathematical form to write down
      the translation from any-recursion to tail-recursion?

      IMHO this must be possible to write down in some
      mathematical form, so that it can be applied to many
      different problems (e.g. for string concatenation,
      as in the example above)?

      Any Hints?

      Ciao,
      Oliver
    • Remi VANICAT
      ... it is auxiliaire. Dict tell me : moi@debian:~/lang/ocaml/test$ dict auxiliary [...] 1. A helper; an assistant; a confederate in some action or enterprise.
      Message 2 of 8 , Sep 3, 2002
      • 0 Attachment
        Stalkern 2 <stalkern2@...> writes:

        > Il Wednesday 04 September 2002 01:42, Remi VANICAT ha scritto:
        >> let sum n =
        >> let rec aux n acc =
        >> if n = 0 then acc
        >> else aux (n-1) (acc+n) in
        >> aux n 0
        >
        >
        > An odd question: I've often seen this nick, "aux", used by French speaking
        > programmers. Where does it come from ?
        > I can't translate it immediately into its signification. I think about
        > "augmenteur" ou "auxiliaire" but I'd like to hear from you.

        it is auxiliaire.
        Dict tell me :
        moi@debian:~/lang/ocaml/test$ dict auxiliary
        [...]
        1. A helper; an assistant; a confederate in some action or
        enterprise.
        [...]
        4. (Math.) A quantity introduced for the purpose of
        simplifying or facilitating some operation, as in
        equations or trigonometrical formul[ae]. --Math. Dict.

        here it is not a quantity but a function, so it should be good in
        English too (but if you have a better translation, tell me, I will try
        to use it).

        --
        Rémi Vanicat
        vanicat@labri.u-bordeaux.fr
        http://dept-info.labri.u-bordeaux.fr/~vanicat
      • Ryan Tarpine
        ... Yet you won t get an important feature of OCaml if you don t know it :) Stack overflows aren t fun for anyone, plus tail recursion often makes things
        Message 3 of 8 , Sep 4, 2002
        • 0 Attachment
          >From: Oliver Bandel <oliver@...-berlin.de>
          >Subject: Re: "ocaml_beginners"::[] [OT]: tail-recursiveness
          >
          >Hello Ryan,
          >
          >
          >On Tue, 3 Sep 2002, Ryan Tarpine wrote:
          >
          > > >From: Oliver Bandel <oliver@...-berlin.de>
          > > >
          > > >Hello,
          > >
          > > Hi. Why did you call this question OT? ;)
          >
          >Hmhh, because it's not language-specific and is more
          >an algorithmic question.

          Yet you won't get an important feature of OCaml if you don't know it :)
          Stack overflows aren't fun for anyone, plus tail recursion often makes
          things faster, I believe

          >...
          >
          >OK,
          >
          >then the following is *not* tail-recursive:
          >
          >
          >let times n s = match n with
          > 0 -> ""
          > | _ -> s ^ times (n-1) s
          >

          Correct

          >
          >BTW: does it mke a differnece (in any respect, maybe ocaml-specific?)
          > to write it in this way:
          >
          >
          >let times n s = match n with
          > 0 -> ""
          > | _ -> times (n-1) s ^ s
          >
          >

          It makes no difference, you are still joining (times (n-1) s) after it
          returns to s, only changing whether you prepend or append s. Since you are
          doing *anything* with the value after the last function returns, it cannot
          be tail recursive.

          >
          >And how could a tail-recursive version look like?

          Add an accumulator to keep track of the string made so far:

          let rec times n s acc = match n with
          | 0 -> acc
          | _ -> times (n-1) s (acc^s)
          ;;

          But this must be called as (times how_many the_string "") to work since the
          accumulator needs to start empty. We can write an auxiliary function, like
          R�mi Vanicat said, to get rid of the need for remembering the accumulator.

          let times n s
          let rec aux n acc = match n with
          | 0 -> acc
          | _ -> aux (n-1) s (acc^s)
          in aux n ""
          ;;

          The aux function does all the real work, times just calls it with an empty
          accumulator for you.

          >
          >And: Is there a mathematical form to write down
          >the translation from any-recursion to tail-recursion?
          >
          >IMHO this must be possible to write down in some
          >mathematical form, so that it can be applied to many
          >different problems (e.g. for string concatenation,
          >as in the example above)?
          >
          >Any Hints?

          Looking on Google quickly, I see
          http://www.owlnet.rice.edu/~comp210/96spring/Labs/lab09.html
          which says

          You can automatically convert an ordinary recursive function into a
          tail-recursive one by following these steps:
          1. Turn the original function into a local helper function.
          2. Add an accumulator argument to the helper function.
          3. Change the helper function's recursive call into a tail-recursive
          call; be sure to update the accumulator appropriately.
          4. Make the body of the main function just a call to the helper, with
          appropriate initial values.

          You can read the page, but it is written for Scheme. Most helpful pages
          seem to be for Scheme people! I would say it's a good idea to learn Scheme
          sometime :)

          >
          >Ciao,
          > Oliver
          >

          Amike,

          Ryan Tarpine

          _________________________________________________________________
          MSN Photos is the easiest way to share and print your photos:
          http://photos.msn.com/support/worldwide.aspx
        • Oliver Bandel
          Hi, ... [...] ... [...] ... I thought, maybe language-specific things could make a difference here. ... OK. ... Yes, this is clear. ... Yes, clear. [...] ...
          Message 4 of 8 , Sep 4, 2002
          • 0 Attachment
            Hi,

            On Wed, 4 Sep 2002, Ryan Tarpine wrote:

            > >From: Oliver Bandel <oliver@...-berlin.de>
            > >Subject: Re: "ocaml_beginners"::[] [OT]: tail-recursiveness
            [...]
            > >On Tue, 3 Sep 2002, Ryan Tarpine wrote:
            > >
            > > > >From: Oliver Bandel <oliver@...-berlin.de>
            [...]
            > >let times n s = match n with
            > > 0 -> ""
            > > | _ -> times (n-1) s ^ s
            > >
            > >
            >
            > It makes no difference, you are still joining (times (n-1) s) after it
            > returns to s, only changing whether you prepend or append s. Since you are
            > doing *anything* with the value after the last function returns, it cannot
            > be tail recursive.

            I thought, maybe language-specific things could make a difference here.

            >
            > >
            > >And how could a tail-recursive version look like?
            >
            > Add an accumulator to keep track of the string made so far:
            >
            > let rec times n s acc = match n with
            > | 0 -> acc
            > | _ -> times (n-1) s (acc^s)
            > ;;

            OK.

            >
            > But this must be called as (times how_many the_string "") to work since the
            > accumulator needs to start empty. We can write an auxiliary function, like
            > Rémi Vanicat said, to get rid of the need for remembering the accumulator.

            Yes, this is clear.

            >
            > let times n s
            > let rec aux n acc = match n with
            > | 0 -> acc
            > | _ -> aux (n-1) s (acc^s)
            > in aux n ""
            > ;;
            >
            > The aux function does all the real work, times just calls it with an empty
            > accumulator for you.

            Yes, clear.


            [...]
            > >Any Hints?
            >
            > Looking on Google quickly, I see
            > http://www.owlnet.rice.edu/~comp210/96spring/Labs/lab09.html
            > which says

            Ok.

            >
            > You can automatically convert an ordinary recursive function into a
            > tail-recursive one by following these steps:
            > 1. Turn the original function into a local helper function.
            > 2. Add an accumulator argument to the helper function.
            > 3. Change the helper function's recursive call into a tail-recursive
            > call; be sure to update the accumulator appropriately.
            > 4. Make the body of the main function just a call to the helper, with
            > appropriate initial values.


            Yes, that is a good cooking recipe.

            This and the "real world examples", which were given
            here, clears a lot.


            >
            > You can read the page, but it is written for Scheme. Most helpful pages
            > seem to be for Scheme people! I would say it's a good idea to learn Scheme
            > sometime :)

            Yes, I have started functional programming with scheme.
            And I remember the things with the accumulator. They were
            written in the book about Computer Languages (Steel & Steel
            I think). But a) I didn't read it complete and b) I was
            a littlebid confused about thjis accumulator-stuff.

            It was unclear to me, if this really was the tail-recursion.
            (They (IMHO) didn't mentioned it in the (section-/chapter-title/-text);
            they mentioned it somwhere in the text (so they could make it clearer,
            I think.))

            After browsing through Haskell- and OCaml-programming
            scheme got more and more uninteresting. ;-)

            Scheme maybe is good for embedded FPL-programming,
            but I like Ocaml very. :) And If I have a PC/workstation,
            I would prefer OCaml, because there are no problems
            with memory-size and such...


            Ciao,
            Oliver
          Your message has been successfully submitted and would be delivered to recipients shortly.