how to get the declaration of a list done during the unnesting recursively?

Question

I have been getting my head around to do the recursion without using any global variable. If am passing the lists the lists of lists ... and resultantly, i should have all the elements from the input in a single list. The problem is every time i call the function the list is declared from the start.

    def unnest (alist):  
        List_ = list()

        for elements in alist: 
            if type(elements) == list: 
                unnest(elements)
            else: 
                List_.append(elements)
        return List_
    if __name__=='__main__':
        unnest([1,2,[3,4,5,[6,7,[8,9,[10,11,[12,[13,[14]]]]]]]])

my goal is to turn the given input list into [1,2,3,4,5,6,7,8,9,10,11,12,13,14] — G.Jan, Aug 31 '16 at 06:59
See [Flatten (an irregular) list of lists in Python](http://stackoverflow.com/q/2158395/4014959) for generator solutions. — PM 2Ring, Aug 31 '16 at 07:06

Jean-François Fabre · Answer 1 · 2016-08-31T07:06:10.033

4

You have to use the returned List_, in subsequent calls, and extend the current list:

def recursion (alist):
    List_ = list()

    for elements in alist:
        if type(elements) == list:
            List_.extend(recursion(elements))  # extend list with recursive call
        else:
            List_.append(elements)  # just add "leaf" element
    return List_

if __name__=='__main__':
    z=recursion([1,2,[3,4,5,[6,7,[8,9,[10,11,[12,[13,[14]]]]]]]])
    print(z)

output:

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

edited Aug 31 '16 at 07:06

answered Aug 31 '16 at 06:59

Jean-François Fabre

137,073
23
153
219

1

you did not even use the return value in the first place, I just did not see the line (since it was just before the main). I added another one it works because the second one is never reached. – Jean-François Fabre Aug 31 '16 at 07:02

Rahul K P · Answer 2 · 2016-08-31T07:43:05.617

2

Try this, There are inbuilt module support for making flattern.

In [47]: from compiler.ast import flatten
In [48]: lst = [1,2,[3,4,5,[6,7,[8,9,[10,11,[12,[13,[14]]]]]]]]
In [49]: flatten(lst)
Out[49]: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

Recursion method,

def flatern(l,ml):
    for i in l:
        if isinstance(i,list):
            flatern(i,ml)
        else:
            ml.append(i)
    return ml

Result

In [52]: flatern(lst,[])
Out[52]: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

edited Aug 31 '16 at 07:43

answered Aug 31 '16 at 07:11

Rahul K P

15,740
4
35
52

solves this particular problem, nice idea: +1. But I think the OP idea was to create a recursion example. You just killed it for him :) – Jean-François Fabre Aug 31 '16 at 07:14
@Jean-FrançoisFabre You are exactly right. Updated my answer with recursion method also. – Rahul K P Aug 31 '16 at 07:33

Erik Kaplun · Answer 3 · 2016-08-31T07:10:52.573

1

you need to pass an accumulator list to the recursive bit of your computation:

def flatten(xs):
    accum = []
    def rec(xs):
        for x in xs:
            if isinstanceof(x, list):
                rec(x)
            else:
                accum.append(x)
    rec(xs)
    return accum

then use flatten instead of rec:

flatten([1,2,[3,4,[5,6,7]]])

edited Aug 31 '16 at 07:10

answered Aug 31 '16 at 07:02

Erik Kaplun

37,128
15
99
111

see my edits, but in any case, I disagree that my code is unreadable; any code can get unreadable quickly if you're not careful – Erik Kaplun Aug 31 '16 at 07:06
Looks much better now! All I was pointing out was that mutating function arguments while recursing, and using that as a sort of *store* for final results can quickly grow unreadable (even though it might be fully readable now) – UltraInstinct Aug 31 '16 at 07:10

Laurens Koppenol · Answer 4 · 2016-08-31T07:19:16.003

1

Your code fixed: You have to append the next recursion level, so the return of a deeper recursion is appended all the way to the top level

def unnest (alist):  
    List_ = list()

    for elements in alist: 
        if type(elements) == list: 
            List_.extend(unnest(elements))
        else: 
            List_.append(elements)


    return List_

unnest([1,2,[3,4,5,[6,7,[8,9,[10,11,[12,[13,[14]]]]]]]])

returns

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

edited Aug 31 '16 at 07:19

answered Aug 31 '16 at 07:04

Laurens Koppenol

2,946
2
20
33

this will get slow with larger lists – Erik Kaplun Aug 31 '16 at 07:10
2

`List_ = List_ + (unnest(elements))` is really sub-optimal because it destroys previous ref of `List_` to create another bigger one each time. `List_ += unnest(elements)` is better (or use `extend`) – Jean-François Fabre Aug 31 '16 at 07:12

napuzba · Answer 5 · 2016-08-31T07:45:41.017

You can use inner function which will do the recursion. This has several adventages:

The function signature will not change
No use of global variables
You will not create a new list each recursion call (memory friendly)

def flatten(old_list):    
    def flattenA(old_list,new_list):
        for item in old_list: 
            if isinstance(item,list):
                flattenA(item , new_list)
            else: 
                new_list.append(item)
        return new_list
    return flattenA(old_list,[])

if __name__=='__main__':
    print( flatten([1,2,[3,4,5,[6,7,[8,9,[10,11,[12,[13,[14]]]]]]]]) )
# prints [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

Benjamin · Answer 6 · 2016-08-31T07:28:18.297

1

list1=[1,2,[3,4,5,[6,7,[8,9,[10,11,[12,[13,[14]]]]]]]]
l=[]
  def recursion(list1,l):
      for i in list1:
          if type(i) is list:
             recursion(i,l)
          else:
             l.append(i)

 recursion(list1,l)
 print(l)

output

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]

edited Aug 31 '16 at 07:28

answered Aug 31 '16 at 07:19

Benjamin

2,257
1
15
24

how to get the declaration of a list done during the unnesting recursively?

6 Answers6