Recursive function returning a list

[Fabian Steiner]

Hello!

I have got a Python "Device" Object which has got a attribute (list)
called children which my contain several other "Device" objects. I
implemented it this way in order to achieve a kind of parent/child
relationship.

Now I would like to get all children of a given "Device" object and
thought that it would be the best way to use recursive function.

This is what I got so far:

def getAllChildren(self, children=[]):
if self.children:
children.extend(self.children)
for child in self.children:
child.getAllChildren(children)
return children

Unfortunately, it doesn't work like expected since the default parameter
children=[] is evaluated only once. That's why the children list becomes
larger and larger after calling the method several times but I can't
think of another possibility.

Do you have any ideas?

 

[Steve Holden]

Hello!

I have got a Python "Device" Object which has got a attribute (list)
called children which my contain several other "Device" objects. I
implemented it this way in order to achieve a kind of parent/child
relationship.

Now I would like to get all children of a given "Device" object and
thought that it would be the best way to use recursive function.

This is what I got so far:

def getAllChildren(self, children=[]):
if self.children:
children.extend(self.children)
for child in self.children:
child.getAllChildren(children)
return children

Unfortunately, it doesn't work like expected since the default parameter
children=[] is evaluated only once. That's why the children list becomes
larger and larger after calling the method several times but I can't
think of another possibility.

Do you have any ideas?

This is a standard question, and has a standard answer: replace

def getAllChildren(self, children=[]):

with

def getAllChildren(self, children=None):
if children is None:
children = []

That way a new empty list is created for each call that receives no
"children" argument. Otherwise the same (once-empty) list is used for
them all.

regards
Steve

 

[Marc 'BlackJack' Rintsch]

This is what I got so far:

def getAllChildren(self, children=[]):
if self.children:
children.extend(self.children)
for child in self.children:
child.getAllChildren(children)
return children

Unfortunately, it doesn't work like expected since the default parameter
children=[] is evaluated only once. That's why the children list becomes
larger and larger after calling the method several times but I can't
think of another possibility.

Do you have any ideas?

def get_all_children(self, accumulator=None):
if accumulator is None:
accumulator = list()
accumulator.extend(self.children)
for child in self.children:
child.get_all_children(accumulator)
return accumulator

Ciao,
Marc 'BlackJack' Rintsch

 

[Boris Borcic]

Do you have any ideas?

you could use a recursive generator, like

def genAllChildren(self) :
for child in self.children :
yield child
for childchild in child.genAllChildren() :
yield childchild

 

[Bruno Desthuilliers]

you could use a recursive generator, like

def genAllChildren(self) :
for child in self.children :
yield child
for childchild in child.genAllChildren() :
yield childchild

Or how to *not* address the real problem...

Boris, using a generator may be a pretty good idea, but *not* as a way
to solve a problem that happens to be a FAQ !-)

 

[Boris Borcic]

Hello Bruno,

Or how to *not* address the real problem...

Boris, using a generator may be a pretty good idea, but *not* as a way
to solve a problem that happens to be a FAQ !-)

Sorry, but I don't understand your reasoning. How can you exclude that the OP
/may/ find that a generator neatly solves his problem ? The use of a default
value was not an end in itself, was it ?- and the quirks of default values being
FAQ stuff don't change that. Sure if nobody had covered that aspect, but a
couple other posters did...

Mmmmhhh somehow it feels like if there is any issue here, it is about defending
the credo "there ought to exist only one obvious way to do it" ?...

Cheers, BB

 

[Bruno Desthuilliers]

Boris Borcic a écrit :

Hello Bruno,



Sorry, but I don't understand your reasoning.

It's quite simple. The OP's problem is well-known (it's a FAQ), and easy
to solve. The righ answer to it is obviously to give a link to the FAQ
(or take time to re-explain it for the zillionth time), not to propose a
workaround.

How can you exclude that
the OP /may/ find that a generator neatly solves his problem ?

I don't exclude it, and explicitly mentioned in whole letters that, I
quote, it "may be a pretty good idea". And actually, the OP's problem is
really with default values evaluation scheme - something that every
Python programmer should know, because there are cases where you cannot
solve it with a generator-based solution !-)

The use
of a default value was not an end in itself, was it ?

If the OP has other reasons to want to use an accumulator based solution
- which we don't know - then the possibility to use a default value is
important.

- and the quirks of
default values being FAQ stuff don't change that. Sure if nobody had
covered that aspect, but a couple other posters did...

Yes, but you forgot to mention that - and I would not have post any
comment on your solution if you had explicitly mentioned the FAQ or
these other answers.

Mmmmhhh somehow it feels like if there is any issue here, it is about
defending the credo "there ought to exist only one obvious way to do it"
?...

Nope, it's about trying to make sure that anyone googling for a similar
problem will notice the canonical solution somehow.

 

[malkarouri]

Boris Borcic a écrit :

It's quite simple. The OP's problem is well-known (it's a FAQ), and easy
to solve. The righ answer to it is obviously to give a link to the FAQ
(or take time to re-explain it for the zillionth time), not to propose a
workaround.


I don't exclude it, and explicitly mentioned in whole letters that, I
quote, it "may be a pretty good idea". And actually, the OP's problem is
really with default values evaluation scheme - something that every
Python programmer should know, because there are cases where you cannot
solve it with a generator-based solution !-)


If the OP has other reasons to want to use an accumulator based solution
- which we don't know - then the possibility to use a default value is
important.


Yes, but you forgot to mention that - and I would not have post any
comment on your solution if you had explicitly mentioned the FAQ or
these other answers.


Nope, it's about trying to make sure that anyone googling for a similar
problem will notice the canonical solution somehow.

Sorry, but I kinda agree with Boris here. Not that I am anybody here,
really.

If the question is to use an accumulator based solution, then yes, the
default values answer is definitely the canonical solution.
If the question is to write a recursive function that returns a list,
an accumulator based solution and a generator based solution are two
different ways for doing that. I don't think there is actually a FAQ
saying you must use the accumulator solution.
Actually, the accumulator based solution kind of comes to me
automatically as standard in any programming language, and I believe
that this was established as standard in python, _before_ the
introduction of generators.

Now, personally I find the generator-based solution more intuitive for
me (in the eys of the beholder. And, looking at the subject of the
thread, guess what was the question?

k

 

[Steve Holden]

Boris Borcic a écrit :

Hello Bruno,

Bruno Desthuilliers wrote: [...]

Or how to *not* address the real problem...

Boris, using a generator may be a pretty good idea, but *not* as a way
to solve a problem that happens to be a FAQ !-)

Sorry, but I don't understand your reasoning.

It's quite simple. The OP's problem is well-known (it's a FAQ), and easy
to solve. The righ answer to it is obviously to give a link to the FAQ

So, why didn't you?

(or take time to re-explain it for the zillionth time), not to propose a
workaround.

Or did I miss something?

regards
Steve

 

[Boris Borcic]

Boris Borcic a écrit :

It's quite simple. The OP's problem is well-known (it's a FAQ),

This is really an oversimplification. What's the case is that his showstopper
was covered by the FAQ list. The OP's "problem" is actually a stack of
problems/subproblems and was presented as such.

and easy
to solve.

I did consider a couple distinct ways to solve "it" while passing lists around -
did you notice that the OP's code made no clear choice as to whether it wanted
to pass them by reference or as return values ? That's how a generator struck me
as most pythonic if you want ("In the face of ambiguity, refuse the temptation
to guess").

The righ answer to it is obviously to give a link to the FAQ
(or take time to re-explain it for the zillionth time), not to propose a
workaround.

Given your usage of code simplicity in another thread as (roughly) a measure of
pythonic virtue, I feel it warranted to ask why should one recognize simpler
code as "the workaround" (assuming it fits the bill) ?

Because it doesn't cross the FAQ, seems to be your answer...

I don't exclude it, and explicitly mentioned in whole letters that, I
quote, it "may be a pretty good idea". And actually, the OP's problem is
really with default values evaluation scheme - something that every
Python programmer should know, because there are cases where you cannot
solve it with a generator-based solution !-) ...
>
> Yes, but you forgot to mention that - and I would not have post any
> comment on your solution if you had explicitly mentioned the FAQ or
> these other answers.

At this point I recognize that our difference may very well have deep roots
relating to cognitive style, educational policy, etc. Generally speaking I
welcome debate on such premisses as an occasion to learn more (not so much from
my contradictor than from the debate itself), but a precondition is that the
partner/contradictor understands my motive (what I can't count on since the idea
of learning from the debate itself is pretty typical such cognitive style
divides). Besides, I don't quite have the time right now.

The short form is : "I strongly disagree with you".

Best, BB

 

[Bruno Desthuilliers]

Sorry, but I kinda agree with Boris here.

On what ?

Not that I am anybody here,
really.

Err... Are you you at least ?-)

If the question is to use an accumulator based solution, then yes, the
default values answer is definitely the canonical solution.
If the question is to write a recursive function that returns a list,
an accumulator based solution and a generator based solution are two
different ways for doing that.

Note that the generator-based solution doesn't return a list. (And yes,
I know, it's just a matter of wrapping the call to obj.genAllChildrens()
in a list constructor).

I don't think there is actually a FAQ
saying you must use the accumulator solution.

Did I say so ? The FAQ I mention is about default values evaluation, and
it's the problem the OP was facing. Please re-read my post more carefully.

Actually, the accumulator based solution kind of comes to me
automatically as standard in any programming language, and I believe
that this was established as standard in python, _before_ the
introduction of generators.

FWIW, you don't need to pass an accumulator around to solve this problem:

def getAllChildren(self):
children = []
if self.children:
children.extend(self.children)
for child in self.children:
children.extend(child.getAllChildren())
return children

 

[Bruno Desthuilliers]

Boris Borcic a écrit :

Hello Bruno,

Bruno Desthuilliers wrote:

[...]

Or how to *not* address the real problem...

Boris, using a generator may be a pretty good idea, but *not* as a way
to solve a problem that happens to be a FAQ !-)

Sorry, but I don't understand your reasoning.

It's quite simple. The OP's problem is well-known (it's a FAQ), and
easy to solve. The righ answer to it is obviously to give a link to
the FAQ

So, why didn't you?

(or take time to re-explain it for the zillionth time), not to propose
a workaround.

Or did I miss something?

The fact that someone already did so ?

 

[Boris Borcic]

Nope, it's about trying to make sure that anyone googling for a similar
problem will notice the canonical solution somehow.

Hey, I challenge you to cook up a plausible query even loosely fitting your
"googling for a similar problem" that would return my answer but not that of the
other posters (nor the faq itself, oeuf corse).

Best, BB

 

[malkarouri]

(e-mail address removed) wrote: [...]

Sorry, but I kinda agree with Boris here.

On what ?

My emphasis is on "we don't know".

Err... Are you you at least ?-)

I am. Thanks for your concern

Note that the generator-based solution doesn't return a list. (And yes,
I know, it's just a matter of wrapping the call to obj.genAllChildrens()
in a list constructor).

And you can do the wrapping in a function that returns a list, to be
more pedantic. And yes, I know you know.

Did I say so ? The FAQ I mention is about default values evaluation, and
it's the problem the OP was facing. Please re-read my post more carefully.

Actually, I have read your post right first time. And I do know you
didn't say that (a FAQ for accumulators). I raised it just in case.
What I don't agree with is that it is not the problem the OP was
facing. The discussion was: is the real problem the default values
problem, which he already got a solution for. Or was the real problem
the list returning recursion problem, for which he (or subsequent
google searchers, who are more likely to come to this thread after
searching for "Recursive function returning a list") may benefit from a
generator approach.

Actually, the accumulator based solution kind of comes to me
automatically as standard in any programming language, and I believe
that this was established as standard in python, _before_ the
introduction of generators.

FWIW, you don't need to pass an accumulator around to solve this problem:

def getAllChildren(self):
children = []
if self.children:
children.extend(self.children)
for child in self.children:
children.extend(child.getAllChildren())
return children

Thanks for the function, though I regard it as kind of trivial for the
level of discussion that we are having now. The problem solved by the
accumulator is _not_ the building of a list recursively. It is doing so
efficiently. Which is definitely not done by creating multiple
temporary lists just to add them. I am sure you know the theory. More
of relevance is that the generator based solution has also the same
efficiency, so they are both better than the trivial solution.
You have a point though. Your function is a solution. Just I don't
regard it as the preferred solution for the problem as I see it. YMMV.

To recap, the OP (and subsequent google searchers, if they pass by) has
now the preferred solution according to you. To my satisfaction, they
will also read the other solution, which looks more pythonic to me. As
I see it, any additional discussion now suffers from diminishing
returns.

Regards,
k

 

[Bruno Desthuilliers]

(e-mail address removed) wrote:
[...]

Sorry, but I kinda agree with Boris here.

On what ?

On the argument that you are (implicitly?) disagreeing with him

it's getting messy - too much level of indirection !-)

on,
obviously. That the OP problem is not definitely the default values
question.

Ok, I do agree that it's only *one* part of the problem - the other
(implied) being "what other possible solutions".

As you say:




My emphasis is on "we don't know".

At least we do agree on something !-)

I am.
Great.

Thanks for your concern
!-)



Actually, I have read your post right first time. And I do know you
didn't say that (a FAQ for accumulators). I raised it just in case.
What I don't agree with is that it is not the problem the OP was
facing. The discussion was: is the real problem the default values
problem, which he already got a solution for. Or was the real problem
the list returning recursion problem, for which he (or subsequent
google searchers, who are more likely to come to this thread after
searching for "Recursive function returning a list") may benefit from a
generator approach.
agreed.

(snip)

Thanks for the function, though I regard it as kind of trivial for the
level of discussion that we are having now. The problem solved by the
accumulator is _not_ the building of a list recursively. It is doing so
efficiently. Which is definitely not done by creating multiple
temporary lists just to add them. I am sure you know the theory. More
of relevance is that the generator based solution has also the same
efficiency, so they are both better than the trivial solution.
You have a point though. Your function is a solution. Just I don't
regard it as the preferred solution for the problem as I see it.

Nor do I.

YMMV.

It doesn't

To recap, the OP (and subsequent google searchers, if they pass by) has
now the preferred solution according to you.

Please not that I didn't meant to present it as "the prefered solution".