Rekursive Generator-Funktionen

[windner]

Im Internet kursiert PocketPCPyton (v 2.2 aufgebohrt) für Windows CE.

Während einer längeren Zugfahrt wollte ich so etwas wie "find text in files" implementieren, damit ich die Dok. durchsuchen kann. Leider fehlt in os die Funktion walk(), also wollte ich einen Ersatz schaffen. Dabei wollte ich eine rekursive Generator-Funktion schreiben, um mir eine lange Liste zu ersparen. Das ist aber nicht so einfach, wie es klingt.

Rekursives Durchlaufen ist ja einfach, ich verwende zB eine Liste:

Code: Alles auswählen

>>> baum = (
	1,
	(2, 3, (4, 5, 6)),
	7,
	8,
	((9, 10), 11)) # ein Baum für die Rekursion
>>> import types
>>> def walk(baum, resultat_liste):
	for ent in baum:
		if type(ent) == types.TupleType:
			walk(ent, resultat_liste)
		else:
			resultat_liste.append(ent)
	return resultat_liste # damit ich statt über die liste gleich über walk iterieren kann
>>> l=[]
>>> for ent in walk(baum, l): print ent,

1 2 3 4 5 6 7 8 9 10 11

Soweit ist alles klar. Daran stört mich nur diese Liste, ich denke, dass das mit yield klarer wäre. Also:

Code: Alles auswählen

>>> def iwalk(baum):
	for ent in baum:
		if type(ent) == types.TupleType:
			iwalk(ent)
		else:
			yield ent
>>> for ent in iwalk(baum): print ent,

1 7 8

Da kommen nur die singulären Werte zurück. Das ist mir noch klar, weil ja der Aufruf iwalk(ent) einen ungenützten Iterator erzeugt.

Wie aber macht man eine Funktion iwalk() mit yield, die sich so verhält wie meine Funktion walk()?

[BlackVivi]

Öhm, vielleicht steh ich grade auf'n Schlauch, aber... Wozu? Dieser "Baum" ist für mich kein Baum o_o Du müsstest einfach nur die Verschachtelung rausnehmen und dann könntest du normal iterieren. Aber vielleicht hab ich das einfach nur nicht verstanden...

[windner]

Dieser "Baum" ist für mich kein Baum o_o Du müsstest einfach nur die Verschachtelung rausnehmen und dann könntest du normal iterieren.

Könnte ich. Sollte aber nur ein Beispiel sein, in Wahrheit arbeite ich mit os.listdir() und der Baum ist mein Dateisystem. Weil der Code aber mit einem Tuple-Baum übersichtlicher ist, habe ich es so gepostet.

[keppla]

Wie aber macht man eine Funktion iwalk() mit yield, die sich so verhält wie meine Funktion walk()?

Keine ahnung, obs cooler geht, aber eine Lösung wäre, dass du im generator über den erzeugten untergenerator iterierst, und alles yieldest:

Code: Alles auswählen

def walk(tree):
   for item in tree:
      if type(item) == types.TupleType:
         for result in walk(item):
            yield result
      else:
         yield item

[BlackJack]

@BlackVivi: Wieso ist das kein Baum? Und darum die Verschachtelung per *Programm* zu entfernen geht es ja gerade. Auf windner's ursprüngliches Problem bezogen gleicht das dem Rat keine Unterverzeichnisse zu benutzen sondern alles in `/` oder `C:\` zu speichern.

@windner: Du musst die einzelnen Elemente aus dem ("Sub")Iterator "yield"en:

Code: Alles auswählen

In [503]: def iwalk(forest):
   .....:     for item in forest:
   .....:         if isinstance(item, tuple):
   .....:             for subitem in iwalk(item):
   .....:                 yield subitem
   .....:         else:
   .....:             yield item
   .....:

In [504]: list(iwalk(baum))
Out[504]: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

[windner]

Danke euch beiden! Da bin ich ja schön auf der Leitung gestanden. Habe verstanden.

Wachse, Forest, wachse!

[BlackVivi]

@BlackVivi: Wieso ist das kein Baum? Und darum die Verschachtelung per *Programm* zu entfernen geht es ja gerade. Auf windner's ursprüngliches Problem bezogen gleicht das dem Rat keine Unterverzeichnisse zu benutzen sondern alles in `/` oder `C:\` zu speichern.

Dann hab' ich das tatsächlich falsch gelesen und verstanden. Verzeihung.