Top level of a recursive function

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

[Julio Di Egidio]

On Tuesday, 13 December 2022 at 15:46:49 UTC+1, Michael F. Stemper wrote:

> 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

> def fred(cf,toplevel=True):

To make it slightly more general pass the level number,
then it's quite a common scheme.

> Aside from being ugly, this lets the caller diddle with "toplevel",
> which shouldn't really be externally modifiable.

That's a different issue, that Python is "strictly dynamic"
(there is no such thing as constants or private scope):
which one can "mitigate", courtesy supporting tools,
by decorating constructs with type annotations.

Julio

[Julio Di Egidio]

On Tuesday, 13 December 2022 at 16:35:48 UTC+1, Julio Di Egidio wrote:
> On Tuesday, 13 December 2022 at 15:46:49 UTC+1, Michael F. Stemper wrote:
>
> > 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
> > def fred(cf,toplevel=True):
>
> To make it slightly more general pass the level number,
> then it's quite a common scheme.
>
> > Aside from being ugly, this lets the caller diddle with "toplevel",
> > which shouldn't really be externally modifiable.
>
> That's a different issue, that Python is "strictly dynamic"
> (there is no such thing as constants or private scope):
> which one can "mitigate", courtesy supporting tools,
> by decorating constructs with type annotations.

The function calls itself, anyway indeed another issue is
that the "original caller" could pass false, which is where
the usual pattern is to expose the straight interface to
the user, and that in turn starts the recursion (and DO
NOT use argument defaults, leave it explicit):

def fred(cf):
return fred_(cf, True)

def fred_(cf, toplevel):
...

HTH,

[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 <r...@zedat.fu-berlin.de>
Sent: Tuesday, December 13, 2022 10:25 AM
To: pytho...@python.org
Subject: Re: Top level of a recursive function

Supersedes: <reduce-202...@ram.dialup.fu-berlin.de>

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

[Chris Angelico]

On Wed, 14 Dec 2022 at 03:35, Michael F. Stemper
<michael...@gmail.com> 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

[Mats Wichmann]

On 12/13/22 10:36, Chris Angelico wrote:
> On Wed, 14 Dec 2022 at 03:35, Michael F. Stemper
> <michael...@gmail.com> 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.

[Chris Angelico]

On Wed, 14 Dec 2022 at 05:01, Mats Wichmann <ma...@wichmann.us> wrote:
>
> On 12/13/22 10:36, Chris Angelico wrote:
> > On Wed, 14 Dec 2022 at 03:35, Michael F. Stemper
> > <michael...@gmail.com> 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

[Michael F. Stemper]

On 13/12/2022 09.03, Stefan Ram wrote:

> "Michael F. Stemper" <michael...@gmail.com> 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.

[Julio Di Egidio]

Thanks for always posting on top of any decent answers
with your half-cooked incompetent fraudulent bullshit.

Julio

[Julio Di Egidio]

On Tuesday, 13 December 2022 at 21:28:47 UTC+1, Michael F. Stemper wrote:
> On 13/12/2022 09.03, Stefan Ram wrote:
> > "Michael F. Stemper" <michael...@gmail.com> 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.

When Dunning-Kruger is a compliment: under pretty
much every respect that is the opposite of anything
a sane programmer would write at any level...

Indeed, while Angelico is the typical fraudulent
programmer, you and Ram are the typical retarded
math sheriffs. He's lucky I don't see his posts,
the fucking fraud...

Get extinguished already.

Julio

[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)))'

[Julio Di Egidio]

Sure, an easy immediate generalization, but arguably
more cogent was to think "passing state/context into
pure functions", which is what I have been hinting at in
my opening answer, and *that*'s actually functional
programming, not just maps and folds...

HTH,

Julio

[Rob Cliffe]

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