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

Flatten a list

Python, 49 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
    def flattenlist(L):
        import types
        WhiteTypes = ('StringType', 'UnicodeType', 'StringTypes', 'ListType',
                  'ObjectType', 'TupleType')
        BlackTypes= tuple( [getattr(types, x) for x in dir(types)
                      if not x.startswith('_')
                      and x not in whites] )

        tmp = []
        def core(L):
            if  not hasattr(L,'__iter__'):
                return [L]
            else :
                for i in L:
                    if isinstance(i,BlackTypes):
                        tmp.append(i)
                        continue
                    if type(i) == type(str()):
                        tmp.append(i)
                    else:
                        core(i)
            return tmp
        return core(L)




#Examples x=[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[['x']]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]
>>> flattenlist(x)
['x']
>>> x=(((((1)))))
>>> flattenlist(x)
[1]
>>> x=[(),(),[]]
>>> flattenlist(x)
[]
>>> x=[(1),('1'),[1.0]]
>>> flattenlist(x)
[1, '1', 1.0]
>>> x=[[[[[[(((([1,1]))))]]]]]]
>>> flattenlist(x)
[1, 1]
>>> x=1
>>> flattenlist(x)
[1]
>>> x=flattenlist
>>> flattenlist(x)
[<function flattenlist at 0x16a8320>]
>>> 

9 comments

Giannis Fysakis (author) 13 years, 10 months ago  # | flag

inspired by http://code.activestate.com/recipes/363051-flatten/

it's a combination of recursion and closures it always return a list either cropped down to one level or if the input is small just a list wrapped around it

Note : in line 17 it just checks if it is instance of any of the types we need

i hope you like it :-)

Alan Plum 13 years, 10 months ago  # | flag

I don't like how it makes certain assumptions about the structure of the types module and uses the module to generate a blacklist by subtracting a predefined whitelist. But more importantly, eval is evil and should be avoided, getattr is better suited in this case.

You could probably sanitize that bit a bit like so:

whitelist = ('StringType', 'UnicodeType', 'StringTypes', 'ListType', 'ObjectType', 'TupleType')
blacklist = tuple([getattr(types, x)
                   for x in dir(types)
                   if not x.startswith('_')
                   and x not in whitelist
                 ])

Or if you want to avoid one-liners:

whitelist = ('StringType', 'UnicodeType', 'StringTypes', 'ListType', 'ObjectType', 'TupleType')
blacklist = list()
for x in dir(types):
    if x.startswith('_') or x in whitelist:
        continue
    blacklist.append(getattr(types, x))

This will still break if the module ever contains anything that is not a type (StringTypes is a tuple, btw) and is not prefixed, though. To fix this you could add the restriction type(x) == type (or type(x) != type in the verbose version).

Other than that it is very concise and pretty solid.

Sunjay Varma 13 years, 10 months ago  # | flag

That function is quite big to do something so simple!

I made this other function some time ago, which as I just tested my self, does everything yours does.

# flattens a list eg. flatten(1, 2, ['b','a','c']) = [1, 2, 'a', 'b', 'c']
def flatten(*args):
    x = []
    for l in args:
        if not isinstance(l, (list, tuple)): l = [l]
        for item in l:
            if isinstance(item, (list,tuple)):
                x.extend(flatten(item))
            else:
                x.append(item)
    return x

Hope you don't mind! -Sunjay03

Giannis Fysakis (author) 13 years, 10 months ago  # | flag

Alan Plum Thanks for your Comment while the rest of the code is doing was it supposed to do , yes it's true my assumptions about the types module makes the code bad...

I totally agree that it needs to add some simpler white and blacklist "handling" ... as you proposed . i was just concentrated only on the core function and i totally forget to clean it up so not to put this very bad bad line --> Types =dir(types)[:-5] )-:

I totally regret i will not do it again ;) :-) :P Anyway thanks for your words

Sunjay Varma My intention was to make my version of flattenlist using closures because from what i saw there where already being made other solutions (recursive,recursive-iterator,for loop etc...)from other people .

My version just came up like this because i wasn't concern about less lines of code and i am pretty sure i can make a smaller version if that is my intention

cheers

Giannis Fysakis (author) 13 years, 9 months ago  # | flag

Alan Plum

I updated the code

Christopher Grebs 13 years, 9 months ago  # | flag

It's much easier to just assume that everything with an __iter__ is a valid iterator and once you talk about iterator rather than lists you can minify the flatten function to this:

def flatten_iterator(iter):
    """Flatten an iterator to one without any sub-elements"""
    for item in iter:
        if hasattr(item, '__iter__'):
            for sub in flatten_iterator(item):
                yield sub
        else:
            yield item
Paddy McCarthy 13 years, 7 months ago  # | flag

Should a list flattener flatten strings? Or tuples? ...

Raymond Hettinger 13 years, 6 months ago  # | flag

Answer to Paddy:

The API is wrong. It is upto to the caller to determine which types are atomic. In some circumstances, strings and tuples should be recursed into, and in other circumstances it might not be useful at all.

Michael Puckett 13 years, 3 months ago  # | flag

I come from a lisp background and this is what I came up with:

def flatten(lst):
    if lst:
        car,*cdr=lst
        if isinstance(car,(list,tuple)):
            if cdr: return flatten(car) + flatten(cdr)
            return flatten(car)
        if cdr: return [car] + flatten(cdr)
        return [car]

test:

flatten((1,2,3,(4,5,6,(7,8,(((1,2)))))))

returns:

[1, 2, 3, 4, 5, 6, 7, 8, 1, 2]
Created by Giannis Fysakis on Mon, 31 May 2010 (GPL3)
Python recipes (4591)
Giannis Fysakis's recipes (3)

Required Modules

Other Information and Tasks

  • Licensed under the GPL 3
  • Viewed 10466 times
  • Revision 3 (updated 13 years ago)