How to merge nested tuples

Question

I have a set of nested tuples:

('id', ('name', ('name_float_fml',)), ('user', ('email',)), ('user', ('last_login',)))

I would like to combine lists with similar prefixes, resulting in:

('id', ('name', ('name_float_fml',)), ('user', ('email','last_login')))

Here is another example:

(('baz', ('bing', ('fizz', 'frozz', ('frazz', ('fry', 'bleep', 'blop'))))), ('baz', ('zap', ('zang',))), 'foo', 'bar')

would be merged to:

(('baz', (('bing', ('fizz', 'frozz', ('frazz', ('fry', 'bleep', 'blop')))), ('zap', ('zang')))), 'foo', 'bar')

These are intended to store paths from the root to the tree leaves:

• 'baz' -> 'bing' -> 'fizz', aka. ('baz' ('bing' ('fizz,)))
• 'baz' -> 'zap' -> 'zang', aka ('baz' ('zap', ('zang',)))
• 'baz' -> 'bing' -> 'frazz' -> 'blop', aka ('baz', ('bing', ('frazz', ('blop,))))

I want to merge the elements where the leaves are reached by the same path. I hope this provides some amount of clarification.

I've written some code to do this, but it is ugly, verbose, and probably fragile. Is there some generic, concise, and/or efficient way of doing this? I imagine there may be some sort of itertools magic that I don't know about which would provide some elegant solution.

Note: I'm using python 2.4

Answer 1

Here is a version that works for the examples you posted:

a = ('id', ('name', ('name_float_fml',)), ('user', ('email',)), ('user', ('last_login',)))
b = (('baz', ('bing', ('fizz', 'frozz',('frazz', ('fry', 'bleep', 'blop'))))), ('baz', ('zap', ('zang',))), 'foo', 'bar')

def preserve_path(value):
    if len(value) == 2 and isinstance(value[1], (list, tuple)):
        return [value]
    else:
        return value

def flatten_group(my_list):
    d = {}
    for item in my_list:
        # Only items with one string, followed by one tuple represent a path
        # segment. In all other situations, strings are leaves.
        if isinstance(item, (list, tuple)) and len(item) == 2:
            key, value = item
            if key in d:
                d[key].extend(flatten_group(preserve_path(value)))
            else:
                d[key] = preserve_path(list(flatten_group(value)))
        else:
            yield item

    for item in d.iteritems():
        yield item

print list(flatten_group(a))
# ['id', ('name', ['name_float_fml']), ('user', ['email', 'last_login'])]
print list(flatten_group(b))
# ['foo', 'bar', ('baz', [['bing', ('fizz', 'frozz', ('frazz', ('fry', 'bleep', 'blop')))], ('zap', ['zang'])])]

Edit 3: Updated with the coauthored version that works for both examples, and incorporates your restriction that it only has to consider merging items that are tuples/lists and contain two items. This also prevents additional flattening of merged items.