Gregory Ewing greg.ew...@canterbury.ac.nz:
Marko Rauhamaa wrote:
At any rate, it demonstrates how the idiom has its place in Python.
Perhaps it does, but I think I'd still prefer it to be explicit.
Don't get me wrong. The method doesn't depend on tail call elimination.
It couldn't because
Terry Reedy wrote:
Problems with branching recursion (multiple recursive calls per
call) are rare except for very deep trees and graphs.
And if your recursion is branching, tail calls won't help
you, except in certain special cases (such as the quicksort
example) where you can predict in
Marko Rauhamaa wrote:
At any rate, it demonstrates how the idiom has its place in Python.
Perhaps it does, but I think I'd still prefer it to be
explicit.
The call in Marko's example is not actually a tail call
as written. To make it a tail call, a return would need
to be added:
Marko Rauhamaa wrote:
I don't know how recursion makes a difference
It makes a difference because people don't expect frames
to disappear from tracebacks when they're not consciously
doing recursion.
--
Greg
--
https://mail.python.org/mailman/listinfo/python-list
On 18/07/2015 23:39, Gregory Ewing wrote:
Marko Rauhamaa wrote:
At any rate, it demonstrates how the idiom has its place in Python.
Perhaps it does, but I think I'd still prefer it to be
explicit.
The call in Marko's example is not actually a tail call
as written. To make it a tail call, a
On 2015-07-18 23:39, Gregory Ewing wrote:
Marko Rauhamaa wrote:
At any rate, it demonstrates how the idiom has its place in Python.
Perhaps it does, but I think I'd still prefer it to be
explicit.
The call in Marko's example is not actually a tail call
as written. To make it a tail call, a
On 07/16/2015 08:58 PM, Steven D'Aprano wrote:
Nice of you to illustrate how being pedantic about something, can
make a response useless with regard to the intended original question.
Just because your intention in giving that code was X, doesn't mean that
others cannot use that code to also
On 16/07/2015 17:17, Ian Kelly wrote:
On Thu, Jul 16, 2015 at 3:28 AM, Robin Becker ro...@reportlab.com wrote:
.
I believe the classic answer is Ackermann's function
http://demonstrations.wolfram.com/RecursionInTheAckermannFunction/
which is said to be not primitive
On 07/16/2015 09:34 PM, Terry Reedy wrote:
On 7/16/2015 3:45 AM, Antoon Pardon wrote:
On 07/15/2015 11:19 PM, Terry Reedy wrote:
I believe that this pattern should work with any set of mutually
recursive functions that always call each other in cyclic order. A
more elaborate version does
On 7/16/2015 3:45 PM, Marko Rauhamaa wrote:
Nobody seemed to notice that I just posted a fairly typical tail call
function:
Because non-recursive tail calls are completely normal. Example:
return len(self.children)
Even tail operations like
return a + b
are tail calls if rewritten as
Chris Angelico ros...@gmail.com writes:
My point was that I have yet to see anything that demands TCO and
can't be algorithmically improved.
I don't think anyone claimed you can't simulate TCO with updateable
variables and a while loop. TCO just sometimes lets you write some
things in a
On Sat, Jul 18, 2015 at 10:40 AM, Terry Reedy tjre...@udel.edu wrote:
If children are not always instances of type(self), as when a tree has
separate Node and Leaf classes, then recursive calls to Node instances must
be separated from non-recursive Leaf calls before replacing the recursive
Terry Reedy tjre...@udel.edu:
On 7/16/2015 3:45 PM, Marko Rauhamaa wrote:
Nobody seemed to notice that I just posted a fairly typical tail call
function:
Because non-recursive tail calls are completely normal.
I don't know how recursion makes a difference but that one did happen to
be
On 7/17/2015 4:55 PM, Marko Rauhamaa wrote:
Terry Reedy tjre...@udel.edu:
On 7/16/2015 3:45 PM, Marko Rauhamaa wrote:
Nobody seemed to notice that I just posted a fairly typical tail call
function:
Because non-recursive tail calls are completely normal.
I don't know how recursion makes a
On 07/16/2015 01:07 AM, Steven D'Aprano wrote:
The point is, people keep insisting that there are a vast number of
algorithms which are best expressed using recursion and which require TCO to
be practical, and yet when asked for examples they either can't give any
examples at all, or they give
On Thu, 16 Jul 2015 08:41 pm, Antoon Pardon wrote:
On 07/16/2015 10:07 AM, Steven D'Aprano wrote:
On Wednesday 15 July 2015 19:29, Antoon Pardon wrote:
Suppose I start with the following:
def even(n):
True if n == 0 else odd(n - 1)
def odd(n):
False if n == 0 else even(n - 1)
On 07/15/2015 11:19 PM, Terry Reedy wrote:
On 7/15/2015 5:29 AM, Antoon Pardon wrote:
Can you explain how you would do mutual recursive functions?
Suppose I start with the following:
def even(n):
True if n == 0 else odd(n - 1)
def odd(n):
False if n == 0 else even(n - 1)
How
On Wednesday 15 July 2015 19:29, Antoon Pardon wrote:
Suppose I start with the following:
def even(n):
True if n == 0 else odd(n - 1)
def odd(n):
False if n == 0 else even(n - 1)
Well, both of those always return None, so can be optimized to:
even = odd = lambda x: None
:-)
Robin Becker ro...@reportlab.com:
which is said to be not primitive recursive ie cannot be unwound
into loops; not sure whether that implies it has to be recursively
defined or can perhaps be broken down some other way. For more
eye-glazing
You only need a single while loop plus primitive
..
The point is, people keep insisting that there are a vast number of
algorithms which are best expressed using recursion and which require TCO to
be practical, and yet when asked for examples they either can't give any
examples at all, or they give examples that are not well-suited to
On Thu, Jul 16, 2015 at 8:41 PM, Antoon Pardon
antoon.par...@rece.vub.ac.be wrote:
Fixing the obvious mistake (failing to return anything) leads to the next
mistake. When all you have is a hammer, everything looks like a nail.
def even(n):
return n%2 == 0
def odd(n):
return n%2 !=
On 16/07/2015 09:07, Steven D'Aprano wrote:
.
Fixing the obvious mistake (failing to return anything) leads to the next
mistake. When all you have is a hammer, everything looks like a nail.
def even(n):
return n%2 == 0
def odd(n):
return n%2 != 0
..
what about
def
On 07/16/2015 10:07 AM, Steven D'Aprano wrote:
On Wednesday 15 July 2015 19:29, Antoon Pardon wrote:
Suppose I start with the following:
def even(n):
True if n == 0 else odd(n - 1)
def odd(n):
False if n == 0 else even(n - 1)
Well, both of those always return None, so can be
Antoon Pardon antoon.par...@rece.vub.ac.be writes:
On 07/13/2015 05:44 PM, Th. Baruchel wrote:
Hi, after having spent much time thinking about tail-call elimination
in Python (see for instance http://baruchel.github.io/blog/ ), I finally
decided to write a module for that. You may find it at:
On 07/16/2015 01:11 PM, Chris Angelico wrote:
On Thu, Jul 16, 2015 at 8:41 PM, Antoon Pardon
antoon.par...@rece.vub.ac.be wrote:
Fixing the obvious mistake (failing to return anything) leads to the next
mistake. When all you have is a hammer, everything looks like a nail.
def even(n):
Robin Becker wrote:
I believe the classic answer is Ackermann's function
http://demonstrations.wolfram.com/RecursionInTheAckermannFunction/
which is said to be not primitive recursive ie cannot be unwound into
loops; not sure whether that implies it has to be recursively defined or
can
On Thu, Jul 16, 2015 at 11:35 PM, Antoon Pardon
antoon.par...@rece.vub.ac.be wrote:
Of course they could be rather trivially reimplemented. They would
also become rather ugly and less easy to comprehend.
Here is one way to do the odd, even example.
def even(n):
return odd_even('even',
On 07/16/2015 03:47 PM, Chris Angelico wrote:
On Thu, Jul 16, 2015 at 11:35 PM, Antoon Pardon
antoon.par...@rece.vub.ac.be wrote:
Any collection of functions that tail calls each other can rather
trivially be turned into a state machine like the above. You can
just paste in the code of the
On Fri, Jul 17, 2015 at 12:21 AM, Antoon Pardon
antoon.par...@rece.vub.ac.be wrote:
My point was that I have yet to see
anything that demands TCO and can't be algorithmically improved.
And how is this point relevant? Why should I care about what you have
not seen? Will it give me new insights
On 07/16/2015 04:27 PM, Chris Angelico wrote:
On Fri, Jul 17, 2015 at 12:21 AM, Antoon Pardon
antoon.par...@rece.vub.ac.be wrote:
My point was that I have yet to see
anything that demands TCO and can't be algorithmically improved.
And how is this point relevant? Why should I care about what
On Thu, Jul 16, 2015 at 3:28 AM, Robin Becker ro...@reportlab.com wrote:
..
The point is, people keep insisting that there are a vast number of
algorithms which are best expressed using recursion and which require TCO
to
be practical, and yet when asked for examples they either
On 7/16/2015 2:02 PM, Ethan Furman wrote:
On 07/16/2015 06:35 AM, Antoon Pardon wrote:
Here is one way to do the odd, even example.
def even(n):
return odd_even('even', n)
def odd(n):
return odd_even('odd', n)
def odd_even(fn, n):
while fn is not None:
if fn ==
Nobody seemed to notice that I just posted a fairly typical tail call
function:
def setvalue(self, keyseq, value, offset=0):
try:
next = keyseq[offset]
except IndexError:
On 07/16/2015 06:35 AM, Antoon Pardon wrote:
On 07/16/2015 01:11 PM, Chris Angelico wrote:
Unless, of course, *all* TCO examples, even real-world ones, could be
trivially reimplemented some other way, a theory which is gaining
currency...
Of course they could be rather trivially
On 07/16/2015 12:45 PM, Terry Reedy wrote:
On 7/16/2015 2:02 PM, Ethan Furman wrote:
On 07/16/2015 06:35 AM, Antoon Pardon wrote:
Here is one way to do the odd, even example.
def even(n):
return odd_even('even', n)
def odd(n):
return odd_even('odd', n)
def odd_even(fn, n):
On 7/16/2015 3:45 AM, Antoon Pardon wrote:
On 07/15/2015 11:19 PM, Terry Reedy wrote:
On 7/15/2015 5:29 AM, Antoon Pardon wrote:
Can you explain how you would do mutual recursive functions?
Suppose I start with the following:
def even(n):
True if n == 0 else odd(n - 1)
def odd(n):
On 07/13/2015 05:44 PM, Th. Baruchel wrote:
Hi, after having spent much time thinking about tail-call elimination
in Python (see for instance http://baruchel.github.io/blog/ ), I finally
decided to write a module for that. You may find it at:
https://github.com/baruchel/tco
Tail-call
On 7/15/2015 5:29 AM, Antoon Pardon wrote:
On 07/13/2015 05:44 PM, Th. Baruchel wrote:
Hi, after having spent much time thinking about tail-call elimination
in Python (see for instance http://baruchel.github.io/blog/ ), I finally
decided to write a module for that. You may find it at:
Hi, after having spent much time thinking about tail-call elimination
in Python (see for instance http://baruchel.github.io/blog/ ), I finally
decided to write a module for that. You may find it at:
https://github.com/baruchel/tco
Tail-call elimination is done for tail-recursion as well as for
39 matches
Mail list logo
