- 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 - Stalkern 2 <stalkern2@...> writes:

> Il Wednesday 04 September 2002 01:42, Remi VANICAT ha scritto:

it is auxiliaire.

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

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 >From: Oliver Bandel <oliver@...-berlin.de>

Yet you won't get an important feature of OCaml if you don't know it :)

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

Stack overflows aren't fun for anyone, plus tail recursion often makes

things faster, I believe

>...

Correct

>

>OK,

>

>then the following is *not* tail-recursive:

>

>

>let times n s = match n with

> 0 -> ""

> | _ -> s ^ times (n-1) s

>

>

It makes no difference, you are still joining (times (n-1) s) after it

>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

>

>

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.

>

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

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

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.

>

Looking on Google quickly, I see

>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?

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 :)

>

Amike,

>Ciao,

> Oliver

>

Ryan Tarpine

_________________________________________________________________

MSN Photos is the easiest way to share and print your photos:

http://photos.msn.com/support/worldwide.aspx- 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