replacing values in a nested tuple with the whole tuple

Question

Okay,

I am working on a linguistic prover, and I have series of tuples that represent statements or expressions. Sometimes, I end up with an embedded "and" statement, and I am trying to "bubble" it up to the surface. I want to take a tuple that looks like this:

('pred', ('and', 'a', 'b'), 'x')

or, for a more simple example:

( ('and', 'a', 'b'), 'x')

and I want to separate out the ands into two statements such that the top one results in:

('and', ('pred', 'a', 'x',), ('pred', 'b', 'x') )

and the bottom one in:

('and', ('a', 'x'), ('b', 'x') )

I've tried a lot of things, but it always turns out to be quite ugly code. And I am having problems if there are more nested tuples such as:

('not', ('p', ('and', 'a', 'b'), 'x') )

which I want to result in

('not', ('and', ('p', 'a', 'x',), ('p', 'b', 'x') ) )

So basically, the problem is trying to replace a nested tuple with the value of the entire tuple, but the nested one modified. It's very ugly. :(

I'm not super duper python fluent so it gets very convoluted with lots of for loops that I know shouldn't be there. :( Any help is much appreciated!

Answer 1

This recursive approach seems to work.

def recursive_bubble_ands_up(expr):
    """ Bubble all 'and's in the expression up one level, no matter how nested.
    """
    # if the expression is just a single thing, like 'a', just return it. 
    if is_atomic(expr):
        return expr
    # if it has an 'and' in one of its subexpressions 
    #  (but the subexpression isn't just the 'and' operator itself)
    #  rewrite it to bubble the and up
    and_clauses = [('and' in subexpr and not is_atomic(subexpr)) 
                   for subexpr in expr]
    if any(and_clauses):
        first_and_clause = and_clauses.index(True)
        expr_before_and = expr[:first_and_clause]
        expr_after_and = expr[first_and_clause+1:]
        and_parts = expr[first_and_clause][1:]
        expr = ('and',) + tuple([expr_before_and + (and_part,) + expr_after_and 
                                 for and_part in and_parts])
    # apply recursive_bubble_ands_up to all the elements and return result
    return tuple([recursive_bubble_ands_up(subexpr) for subexpr in expr])

def is_atomic(expr):
    """ Return True if expr is an undividable component 
    (operator or value, like 'and' or 'a'). """
    # not sure how this should be implemented in the real case, 
    #  if you're not really just working on strings
    return isinstance(expr, str)

Works on all your examples:

>>> tmp.recursive_bubble_ands_up(('pred', ('and', 'a', 'b'), 'x'))
('and', ('pred', 'a', 'x'), ('pred', 'b', 'x'))
>>> tmp.recursive_bubble_ands_up(( ('and', 'a', 'b'), 'x'))
('and', ('a', 'x'), ('b', 'x'))
>>> tmp.recursive_bubble_ands_up(('not', ('p', ('and', 'a', 'b'), 'x') ))
('not', ('and', ('p', 'a', 'x'), ('p', 'b', 'x')))

Note that this isn't aware of any other "special" operators, like not - as I said in my comment, I'm not sure what it should do with that. But it should give you something to start with.

Edit: Oh, oops, I just realized this only performs a single "bubble-up" operation, for example:

>>> tmp.recursive_bubble_ands_up(((('and', 'a', 'b'), 'x'), 'y' ))
(('and', ('a', 'x'), ('b', 'x')), 'y')
>>> tmp.recursive_bubble_ands_up((('and', ('a', 'x'), ('b', 'x')), 'y'))
('and', (('a', 'x'), 'y'), (('b', 'x'), 'y'))

So what you really want is probably to apply it in a while loop until the output is identical to the input, if you want your 'and' to bubble up from however many levels, like this:

def repeat_bubble_until_finished(expr):
    """ Repeat recursive_bubble_ands_up until there's no change 
    (i.e. until all possible bubbling has been done). 
    """
    while True:
        old_expr = expr
        expr = recursive_bubble_ands_up(old_expr)
        if expr == old_expr:
            break
    return expr

On the other hand, doing that shows that actually my program breaks your 'not' example, because it bubbles the 'and' ahead of the 'not', which you said you wanted left alone:

>>> tmp.recursive_bubble_ands_up(('not', ('p', ('and', 'a', 'b'), 'x')))
('not', ('and', ('p', 'a', 'x'), ('p', 'b', 'x')))
>>> tmp.repeat_bubble_until_finished(('not', ('p', ('and', 'a', 'b'), 'x')))
('and', ('not', ('p', 'a', 'x')), ('not', ('p', 'b', 'x')))

So I suppose you'd have to build in a special case for 'not' into recursive_bubble_ands_up, or just apply your not-handling function before running mine, and insert it before recursive_bubble_ands_up in repeat_bubble_until_finished so they're applied in alternation.

All right, I really should sleep now.