Concatenate Items within nested list python

Question

Given a list such as:

['a', '1' ,['c', 'd',['e',['f', '123']]]]

how would I concatenate the items within each nested list resulting in:

['a1',['cd',['e',['f123']]]]

I can concatenate items within a single list but have been unsuccessful with this so far, any help would be much appreciated!

Answer 1

The nested structure here is good for being traversed by a recursive algorithm:

x = ['a', '1', ['c', 'd', ['e', ['f', '123']]]]

def recurse(y):
    left,right = [],None

    # Here we loop over the elements and whenever we encounter
    # another list, we recurse.  
    for elem in y:
        if isinstance(elem,list):
            right = recurse(elem)
        else:
            left.append(elem)

    # If there is no further nested list, return only the 
    # concatenated values, else return the concatenated values 
    # and the next list in the nest.
    if right is None:
        return ["".join(left)]
    else:
        return ["".join(left),right]

print recurse(x)

The output from this is:

['a1', ['cd', ['e', ['f123']]]]

Answer 2

Here is a non-recursive solution:

Here are the steps:

1. Merge the strings
2. Reverse the list
3. Reduce the strings to nested list.

It may not be elegant than the recursive version, but it won't blow up the stack if the list is deeply nested.

def collapse(x):
    l = deque([x])
    result = []
    y = ""

    while l:
        p = l.popleft()
        for i in p:
            if isinstance(i, list):
                result.append(y)
                y = ""
                l.append(i)
                break
            else:
                y = y + i
    result.append(y)
    return result


x = ['a', '1', ['c', 'd', ['e', ['f', '123']]]]
j = [ i for i in collapse(x)]
j.reverse()
print reduce(lambda x, y: [y, x], j[1:], [j[0]])