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?

[Marc 'BlackJack' Rintsch]

In <e9*************@news.t-online.com>, Fabian Steiner wrote:

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

[Steve Holden]

Fabian Steiner wrote:

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
--
Steve Holden [phone] [phone]
Holden Web LLC/Ltd http://www.holdenweb.com
Skype: holdenweb http://holdenweb.blogspot.com
Recent Ramblings http://del.icio.us/steve.holden

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

Boris Borcic wrote:

>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

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 !-)

--
bruno desthuilliers
python -c "print '@'.join(['.'.join([w[::-1] for w in p.split('.')]) for
p in 'o****@xiludom.gro'.split('@')])"

[Boris Borcic]

Hello Bruno,

Bruno Desthuilliers wrote:

Boris Borcic wrote:

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

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
--
666 ?? - 666 ~ .666 ~ 2/3 ~ 1-1/3 ~ tertium non datur ~ the excluded middle
~ "either with us, or against us" !!

[Bruno Desthuilliers]

Boris Borcic a écrit :

Hello Bruno,

Bruno Desthuilliers wrote:

>Boris Borcic wrote:

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

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
(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]

Bruno Desthuilliers wrote:

Boris Borcic a écrit :

Hello Bruno,

Bruno Desthuilliers wrote:

Boris Borcic wrote:

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

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

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]

Bruno Desthuilliers wrote:

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
--
Steve Holden [phone] [phone]
Holden Web LLC/Ltd http://www.holdenweb.com
Skype: holdenweb http://holdenweb.blogspot.com
Recent Ramblings http://del.icio.us/steve.holden

[Boris Borcic]

Bruno Desthuilliers wrote:

Boris Borcic a écrit :

>Hello Bruno,

Bruno Desthuilliers wrote:

>>Boris Borcic wrote:

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

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),

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

>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 !-)

...

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

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
--
"On naît tous les mètres du même monde"

[Bruno Desthuilliers]

ma********@gmail.com wrote:

Bruno Desthuilliers wrote:

>>Boris Borcic a écrit :

>>>Hello Bruno,

Bruno Desthuilliers wrote:
Boris Borcic wrote:
>>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

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

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
python -c "print '@'.join(['.'.join([w[::-1] for w in p.split('.')]) for
p in 'o****@xiludom.gro'.split('@')])"

[Bruno Desthuilliers]

Steve Holden wrote:

Bruno Desthuilliers wrote:

>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 ?
--
bruno desthuilliers
python -c "print '@'.join(['.'.join([w[::-1] for w in p.split('.')]) for
p in 'o****@xiludom.gro'.split('@')])"

[Boris Borcic]

Bruno Desthuilliers wrote:

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 thatof the
other posters (nor the faq itself, oeuf corse).

Best, BB
--
"On naît tous les mètres du même monde"

[malkarouri]

Bruno Desthuilliers wrote:

ma********@gmail.com wrote:

[...]

Sorry, but I kinda agree with Boris here.

On what ?

On the argument that you are (implicitly?) disagreeing with him on,
obviously. That the OP problem is not definitely the default values
question. As you say:

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

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

>

Not that I am anybody here,
really.

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.

>

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, 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]

ma********@gmail.com wrote:

Bruno Desthuilliers wrote:

>>ma********@gmail.com 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:

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

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

At least we do agree on something !-)

>

>>>Not that I am anybody here,
really.

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

I am.

Great.

Thanks for your concern:)

!-)

>

(snip)

>>>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, 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".
--
bruno desthuilliers
python -c "print '@'.join(['.'.join([w[::-1] for w in p.split('.')]) for
p in 'o****@xiludom.gro'.split('@')])"