Welcome, guest | Sign In | My Account | Store | Cart

I have written Flatten a few dozen times, and also searched the interwebs - I don't feel good about a heavily recursive function for Python, and some of the "type-sniffing" I saw in some codes seemed fishy - so I coded up this version. At least this increases the options. Handles strings, dictionaries, generators, sequences, lists, tuples -- in sensible ways. Handles arbitrarily deep levels of nesting. Does the bare minimum of type-sniffing. With Doctest tests.

Python, 64 lines
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
def flatten(x):
    r"""
    
    >>> flatten("hello")
    'hello'
    >>> flatten({"a":[["hi"]]})
    {'a': [['hi']]}
    >>> flatten(None) is None
    True
    >>> flatten(3)
    3
    >>> flatten([0, [1, ["two"]]])
    [0, 1, 'two']
    >>> flatten( (0, (1, ("two",))) )
    (0, 1, 'two')
    >>> flatten([0, [1, 2], 3, ([4, 5], 6)])
    [0, 1, 2, 3, 4, 5, 6]
    >>> flatten( (0, 1, (i + 1 for i in xrange(1, 3)) ) )
    (0, 1, 2, 3)
    >>> flatten([[[[[0]]]]])
    [0]
    >>> flatten([0, [[{"a":[["hi"]]}]]])
    [0, {'a': [['hi']]}]
    
    """
    
    if isinstance(x, basestring):
        return x
    if hasattr(x, "__iter__"):
        if hasattr(x, "items"):
            return x
    else:
        return x
    
    is_tuple = isinstance(x, tuple)
    
    # leave exception here unhandled
    # if conversion to list fails
    x = list(x)
    x.reverse()
    
    r = []
    while x:
        y = x.pop(-1)
        if isinstance(y, basestring):
            r.append(y)
            continue
        if hasattr(y, "__iter__"):
            if hasattr(y, "items"):
                r.append(y)
                continue
        else:
            r.append(y)
            continue
        # leave exception here unhandled
        # if conversion to list fails
        y = list(y)
        y.reverse()
        x.extend(y)
        
    if is_tuple:
        return tuple(r)
    else:
        return r

Instead of using the call stack through recursion, this version maintains its own stack to handle arbitrarily deep levels of nesting, which seems wise because of the function call overhead in Python implementations. Doctest documents the typical usage and special cases and corner cases. Does the right thing with generators, as documented.

Created by Manuel Garcia on Thu, 9 Sep 2010 (MIT)
Python recipes (4591)
Manuel Garcia's recipes (5)

Required Modules

  • (none specified)

Other Information and Tasks