Re: Top level of a recursive function

2022-12-17 Thread Rob Cliffe via Python-list




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

2022-12-15 Thread Peter Otten

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

2022-12-13 Thread Michael F. Stemper

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

2022-12-13 Thread Chris Angelico
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

2022-12-13 Thread Mats Wichmann

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

2022-12-13 Thread Chris Angelico
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

2022-12-13 Thread Schachner, Joseph (US)
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

2022-12-13 Thread Michael F. Stemper

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