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.
Download
Copy to clipboard1 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.
