Flatten a sequence

[bwbg]

Zur Problemstellung flatten a sequence zu Hauf Lösungen mit Hilfsliste finden kann, hier eine Generator-Lösung:

Code: Alles auswählen

def flatten(xs):
    """
    >>> list(flatten([1, 2, [3, 4], [5, [6, 7]], 8]))
    [1, 2, 3, 4, 5, 6, 7, 8]
    """
    for x in xs:
        try:
            for e in flatten(iter(x)):
                yield e
        except TypeError: # x is not iterable
            yield x

Grüße ... bwbg

[BlackJack]

@bwbg: Probier das mal mit einer Zeichenkette irgendwo als Datum aus.

[bwbg]

Ja, die Endlosrekursion verrate es nur keinem.

[bwbg]

Das Problem bei Zeichenketten ist, das deren Elemente wiederum Zeichenketten sind (welche nur ein Zeichen enthalten) und damit iterierbar sind. Um das Problem mit der Endlosrekursion zu beseitigen, habe ich eine Weiche vorgeschaltet, welche die Länge der Sequenz prüft. Praktisch ist, dass `len` einen auch TypeError wirft, wenn es keine Länge zu ermitteln gibt.

Minimal geänderte Funktion mit neuem test-case:

Code: Alles auswählen

def flatten(xs):
    """
   >>> list(flatten([1, 2, [3, 4], [5, [6, 7]], 8]))
   [1, 2, 3, 4, 5, 6, 7, 8]
   >>> list(flatten([[1, 2], "FooBar", 3, 4]))
   [1, 2, 'F', 'o', 'o', 'B', 'a', 'r', 3, 4]
   """
    for x in xs:
        try:
            if len(x) > 1:
                for e in flatten(iter(x)):
                    yield e
            else:
                yield x[0]
        except TypeError: # x is not iterable OR has no len()
            yield x

Hier stellt sich allerdings die Frage, wie man Zeichenketten behandeln möchte. Derzeit werden diese als Sequenz (von Zeichen) betrachtet. Möglich wäre auch eine Betrachung als "Einheit", jedoch müsste man hier auf den speziellen Typ prüfen, was ich gerne vermeiden möchte.

Grüße ... bwbg

[Sirius3]

Und was passiert mit Listen mit 0 Elementen? Ein IndexError.

[snafu]

Code: Alles auswählen

from collections import Iterable

try:
    STRING_TYPES = (str, unicode)
except NameError:
    # Assume Python 3.x
    STRING_TYPES = (str, bytes)


def flatten(obj):
    for item in obj:
        if isinstance(item, Iterable) and not isinstance(item, STRING_TYPES):
            for subitem in flatten(item):
                yield subitem
        else:
            yield item

[BlackJack]

@snafu: Damit würde man jetzt aber Objekte die zwar iterierbar sind, aber nicht `Iterable`, nicht flachklopfen. Ob ein Objekt tatsächlich (nicht) iterierbar ist, kann man letztendlich nur durch ausprobieren heraus finden. Da gibt es keinen Test den man vorher machen könnte.

[snafu]

@BlackJack: Hast du ein konkretes Beispiel, wo mein Vorab-Test nicht greifen würde?

[EyDu]

Bei dem hier zum Beispiel:

Code: Alles auswählen

from collections import Iterable


class It(object):
    def __getitem__(self, index):
        if index < 5:
            return 2*index
        else:
            raise IndexError

if __name__ == "__main__":
    it = It()

    print isinstance(it, Iterable)
    
    for elem in it:
        print elem

[snafu]

Gut zu wissen...