Elegent way to collapse or expand sub-sequences of a list in Python?

Question

I want to collapse or expand sub-sequences of a list

e.g. ['A', 'B', 'D', 'E', 'H'] -> ['AB', 'DE', 'H'] and vice versa

EDIT: the example above may cause misunderstanding. the following is better:

e.g. ['foo', 'bar', 'wtf'] <-> ['baz', 'wtf']

currently I wrote some ugly code like:

while True:
  for i, x in enumerate(s):
    if x == 'foo' and s[i+1] == 'bar':
      s[i:i+2] = 'baz'
      break
  else:
    break

For people who asking 'why do that thing':

Actually I'm working on a optimizing compiler and this is the peephole part. Writing pattern matching is a little annoying.

P.S. I found the following code works, but a bit ridiculous, why enumerate know our modification?

s = ['foo', 'bar', 'wtf', 'foo', 'bar', 'wtf', 'foo', 'bar', 'wtf']

def collapse():
    for i, x in enumerate(s):
        if s[i] == 'foo' and s[i+1] == 'bar':
            s[i:i+2] = ['baz']

def expand():
    for i, x in enumerate(s):
        if s[i] == 'baz':
            s[i:i+1] = ['foo', 'bar']

collapse()
print s
expand()
print s

Answer 1

See itertools. Specifically, here's a recipe for more or less what you want (actually, what I thought you wanted after your kind of misleading original post!):

from itertools import tee, izip

def pairwise(iterable):
    "s -> (s0,s1), (s1,s2), (s2, s3), ..."
    a, b = tee(iterable)
    next(b, None)
    return izip(a, b)

This will return tuples which you can join().

To undo this, just join() your final sequence and iterate over the individual items (chars).

I will try to come up with an answer to your new/real question.

Answer 2

I think that your way with enumerate is pretty good actually. Enumerate is able to keep track of the modifications because it creates a generator that uses an iterator of the array you input. The problem I see is if you change your array to be:

s = ['foo', 'bar', 'wtf', 'foo', 'bar', 'wtf', 'foo']

then the last 'foo' that doesn't have a 'bar' will give you an exception when your code tries to look at the item beyond the end of the array. I'm not sure how to fix this yet because my attempts haven't been successful.

Edit:

It may not be very elegant, but this code for the collapse() function will work even on the above case:

def collapse():
    i = 1
    L = len(s)
    while i < L:
        if s[i-1] == 'foo' and s[i] == 'bar':
            s[i-1:i+1] = ['baz']
            L -= 1
        i += 1

Answer 3

I wouldn't call this much better but it's a different way to do it, and it also handles the quirk Justin points out. (I was more interested in finding a subsequence from a list, and I couldn't find a good function on Google)

def findsubseq(L, subseq):
    if not subseq: return # just die on zero-len input
    i = -1
    try:
        while True:
            i = L.index(subseq[0], i+1)
            for j in range(1, len(subseq)):
                if L[i+j] != subseq[j]:
                    break
            else:
                yield i
    except ValueError: pass
    except IndexError: pass

def replace(target, changethis, tothis):
    subseqs = [x for x in findsubseq(target, changethis)]
    subseqs.reverse()
    for i in subseqs:
        target[i:i+len(changethis)] = tothis
def collapse():
    global s
    replace(s, ['foo', 'bar'], ['baz'])
def expand():
    global s
    replace(s, ['baz'], ['foo', 'bar'])

s = ['foo', 'bar', 'wtf', 'foo', 'bar', 'wtf',
       'foo', 'bar', 'bar', 'bar', 'foo']
print s
collapse()
print s
expand()
print s

---

C:\Scripts>subseq.py
['foo', 'bar', 'wtf', 'foo', 'bar', 'wtf', 'foo', 'bar', 'bar', 'bar', 'foo']
['baz', 'wtf', 'baz', 'wtf', 'baz', 'bar', 'bar', 'foo']
['foo', 'bar', 'wtf', 'foo', 'bar', 'wtf', 'foo', 'bar', 'bar', 'bar', 'foo']

Edit: generalized it to just a simple replace function