Velocity Reviews > Recursive function returning a list

# Recursive function returning a list

Fabian Steiner
Guest
Posts: n/a

 07-17-2006
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
Guest
Posts: n/a

 07-17-2006
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 +44 150 684 7255 +1 800 494 3119
Holden Web LLC/Ltd http://www.holdenweb.com
Skype: holdenweb http://holdenweb.blogspot.com
Recent Ramblings http://del.icio.us/steve.holden

Marc 'BlackJack' Rintsch
Guest
Posts: n/a

 07-17-2006
In <e9gdpa\$lhb\$01\$(E-Mail Removed)-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

Boris Borcic
Guest
Posts: n/a

 07-18-2006
> 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
Guest
Posts: n/a

 07-18-2006
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 '(E-Mail Removed)'.split('@')])"

Boris Borcic
Guest
Posts: n/a

 07-18-2006
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
Guest
Posts: n/a

 07-18-2006
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

> 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@gmail.com
Guest
Posts: n/a

 07-19-2006
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
>
> > 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
Guest
Posts: n/a

 07-19-2006
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 +44 150 684 7255 +1 800 494 3119
Holden Web LLC/Ltd http://www.holdenweb.com
Skype: holdenweb http://holdenweb.blogspot.com
Recent Ramblings http://del.icio.us/steve.holden

Boris Borcic
Guest
Posts: n/a

 07-19-2006
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) ?

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

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"