Re: Top level of a recursive function
On 14/12/2022 13:49, Stefan Ram wrote:
I also found an example similar to what was discussed here
in pypy's library file "...\Lib\_tkinter\__init__.py":
|def _flatten(item):
|def _flatten1(output, item, depth):
|if depth > 1000:
|raise ValueError("nesting too deep in _flatten")
|if not isinstance(item, (list, tuple)):
|raise TypeError("argument must be sequence")
|# copy items to output tuple
|for o in item:
|if isinstance(o, (list, tuple)):
|_flatten1(output, o, depth + 1)
|elif o is not None:
|output.append(o)
|
|result = []
|_flatten1(result, item, 0)
|return tuple(result)
.
This presumably results in an (avoidable) run-time overhead from
constructing _flatten1 every time _flatten is called (and having it
garbage-collected later).
Best wishes
Rob Cliffe
--
https://mail.python.org/mailman/listinfo/python-list
Re: Top level of a recursive function
On 13/12/2022 15:46, Michael F. Stemper wrote:
It's easy enough -- in fact necessary -- to handle the bottom
level of a function differently than the levels above it. What
about the case where you want to handle something differently
in the top level than in lower levels? Is there any way to tell
from within a function that it wasn't invoked by itself?
I've come up with a hack to support different processing, by
use of an extra argument, as shown in this simplified example:
def fred(cf,toplevel=True):
x = cf[0]
if len(cf)>1:
if toplevel:
return x + fred(cf[1:],False)
else:
return "(" + x + fred(cf[1:],False) + ")"
else:
if toplevel:
return x
else:
return "(" + x + ")"
Aside from being ugly, this lets the caller diddle with "toplevel",
which shouldn't really be externally modifiable.
Are there better ways to do this?
For adepts of functional programming the above is a "fold right"
operation, first hit for "foldr in python":
https://burgaud.com/foldl-foldr-python
With that
>>> from functools import reduce
>>> def foldr(func, items):
return reduce(lambda x, y: func(y, x), items[::-1])
your problem reduces ;) to
>>> foldr("{0}({1})".format, [1,2,3,4])
'1(2(3(4)))'
--
https://mail.python.org/mailman/listinfo/python-list
Re: Top level of a recursive function
On 13/12/2022 09.03, Stefan Ram wrote:
"Michael F. Stemper" writes:
def fred(cf,toplevel=True):
x = cf[0]
if len(cf)>1:
if toplevel:
return x + fred(cf[1:],False)
else:
return "(" + x + fred(cf[1:],False) + ")"
else:
if toplevel:
return x
else:
return "(" + x + ")"
def rest( s ):
return "(" + s[ 0 ] +( rest( s[1:] ) if len( s )> 1 else '' )+ ')'
def nest( s ):
return( s[ 0 ] if s else '' )+( rest( s[1:] )if len( s )> 1 else '' )
Hey, that's slick! And if I define rest within nest, it's not going
to be externally accessible.
Thanks
--
Michael F. Stemper
No animals were harmed in the composition of this message.
--
https://mail.python.org/mailman/listinfo/python-list
Re: Top level of a recursive function
On Wed, 14 Dec 2022 at 05:01, Mats Wichmann wrote: > > On 12/13/22 10:36, Chris Angelico wrote: > > On Wed, 14 Dec 2022 at 03:35, Michael F. Stemper > > wrote: > >> > >> It's easy enough -- in fact necessary -- to handle the bottom > >> level of a function differently than the levels above it. What > >> about the case where you want to handle something differently > >> in the top level than in lower levels? Is there any way to tell > >> from within a function that it wasn't invoked by itself? > >> > > > > Why does it have to be the same function? > > > > def _sort_recursive(stuff, keys, start, end): > > """imagine a nice implementation of some sorting algorithm here""" > > > > def sort(stuff, key=None): > > if key: > > keys = [key(x) for x in stuff] > > else: > > keys = stuff > > return _sort_recursive(stuff, 0, len(stuff)) > > if some support for this position is needed, this is roughly how the > stdlib glob() function is implemented. > Yeah, lots of things are done that way. You'll find a variety of naming conventions around different languages and libraries, including "_low_FUNCTIONNAME" or "_internal_FUNCTIONNAME" etc. It's definitely easier than trying to mess with tracking toplevel status. ChrisA -- https://mail.python.org/mailman/listinfo/python-list
Re: Top level of a recursive function
On 12/13/22 10:36, Chris Angelico wrote: On Wed, 14 Dec 2022 at 03:35, Michael F. Stemper wrote: It's easy enough -- in fact necessary -- to handle the bottom level of a function differently than the levels above it. What about the case where you want to handle something differently in the top level than in lower levels? Is there any way to tell from within a function that it wasn't invoked by itself? Why does it have to be the same function? def _sort_recursive(stuff, keys, start, end): """imagine a nice implementation of some sorting algorithm here""" def sort(stuff, key=None): if key: keys = [key(x) for x in stuff] else: keys = stuff return _sort_recursive(stuff, 0, len(stuff)) if some support for this position is needed, this is roughly how the stdlib glob() function is implemented. -- https://mail.python.org/mailman/listinfo/python-list
Re: Top level of a recursive function
On Wed, 14 Dec 2022 at 03:35, Michael F. Stemper wrote: > > It's easy enough -- in fact necessary -- to handle the bottom > level of a function differently than the levels above it. What > about the case where you want to handle something differently > in the top level than in lower levels? Is there any way to tell > from within a function that it wasn't invoked by itself? > Why does it have to be the same function? def _sort_recursive(stuff, keys, start, end): """imagine a nice implementation of some sorting algorithm here""" def sort(stuff, key=None): if key: keys = [key(x) for x in stuff] else: keys = stuff return _sort_recursive(stuff, 0, len(stuff)) With purely recursive functions (where every call to the function truly could have been a top-level call - a lot of mathematical functions work out this way), it makes sense to call the externally-callable function recursively; but for anything more messy, it's usually easiest to make the recursive part internal, and then have a top-level function that calls into the recursive one. ChrisA -- https://mail.python.org/mailman/listinfo/python-list
RE: Top level of a recursive function
Reducing repetitiveness has made this code harder to read. I had to think about
what it is doing. It might be slightly faster, but in my opinion it is not
worth it.
--- Joseph S.
Teledyne Confidential; Commercially Sensitive Business Data
-Original Message-
From: Stefan Ram
Sent: Tuesday, December 13, 2022 10:25 AM
To: python-list@python.org
Subject: Re: Top level of a recursive function
Supersedes:
r...@zedat.fu-berlin.de (Stefan Ram) writes:
>def rest( s ):
>return "(" + s[ 0 ] +( rest( s[1:] ) if len( s )> 1 else '' )+ ')'
>def nest( s ):
>return( s[ 0 ] if s else '' )+( rest( s[1:] )if len( s )> 1 else '' )
Below, I have tried to reduce repetitiveness a bit.
(PS: Now, one "if" remains; less ifs are not possible
in the case of controlled recursion.)
def rest( s ):
return '(' + nest( s )+ ')'
def nest( s ):
return s[ :1 ]+( rest( s[ 1: ])if s[ 1: ]else '' )
fred = nest
--
https://mail.python.org/mailman/listinfo/python-list
Top level of a recursive function
It's easy enough -- in fact necessary -- to handle the bottom
level of a function differently than the levels above it. What
about the case where you want to handle something differently
in the top level than in lower levels? Is there any way to tell
from within a function that it wasn't invoked by itself?
I've come up with a hack to support different processing, by
use of an extra argument, as shown in this simplified example:
def fred(cf,toplevel=True):
x = cf[0]
if len(cf)>1:
if toplevel:
return x + fred(cf[1:],False)
else:
return "(" + x + fred(cf[1:],False) + ")"
else:
if toplevel:
return x
else:
return "(" + x + ")"
Aside from being ugly, this lets the caller diddle with "toplevel",
which shouldn't really be externally modifiable.
Are there better ways to do this?
--
Michael F. Stemper
I refuse to believe that a corporation is a person until Texas executes one.
--
https://mail.python.org/mailman/listinfo/python-list
