wildcard exclusion in cartesian products

[wkehowski at cox.net]

The python code below is adapted from a Haskell program written by
Tomasz
Wielonka on the comp.lang.functional group. It's more verbose than his
since I wanted to make sure I got it right.

http://groups.google.com/group/comp.lang.functional/browse_frm/thread...

Does anyone know how to turn it into a module (or whatever it's called)
so that I can put it in a
loop and not have to generate the whole list? I've already tried
without success.

The program solves the following problem: generate the subset X of the
cartesian product S^n that excludes n-tuples defined by wildcards. For
example, if I want to exclude from [1,2,3]^3 the wc's [1,"*",2] and
["*",3,"*",3,"*"], where "*" stands for a sequence of zero or more
elements of [1,2,3], then I just type

for x in generateNotMatching([1,2,3,4],4,[[1,'*',2],[3,'*',4]]): print
x

and get the output

                           [1, 1, 1]
                           [1, 1, 3]
                           [1, 2, 1]
                           [1, 2, 3]
                           [1, 3, 1]
                           [2, 1, 1]
                           [2, 1, 2]
                           [2, 1, 3]
                           [2, 2, 1]
                           [2, 2, 2]
                           [2, 2, 3]
                           [2, 3, 1]
                           [2, 3, 2]
                           [3, 1, 1]
                           [3, 1, 2]
                           [3, 2, 1]
                           [3, 2, 2]

This is nice! But all elements are generated before they are printed.

##----------------------------
import sys, os, string

def imap(function, source):
    for element in source:
        yield function(element)

def any(iterable):
     '''True iff at least one element of the iterable is True'''
     for element in iterable:
        if element:
            return True # or element and change the definition
     return False

def all(iterable):
     '''True iff no element of the iterable is True'''
     '''SHOULD BE?: True iff all element of the iterable are True'''
     for element in iterable:
        if not element:
            return False
     return True

def rev(L):
    rL=[]
    for x in L: rL=[x]+rL
    return rL

def advancePattern(x,p):
    if p==[]: return []
    else:
       h=p[0]
       t=p[1:]
       if h != '*':
          if h == x: return [t]
          else: return []
       else: return [p] + [t] + advancePattern(x,t)

def advancePatterns(x,P):
    aP=[]
    for p in P:
        aP += advancePattern(x,p)
    return aP

#    return [advancePattern(x,p) for p in P]

def allStar(p):
    return all( imap((lambda x: x=='*'),p) )

def notNullOrZero(p,n):
    return p !=[] or n==0

def generateNotMatching(A,n,P):
    return gen(A,n,P,[])

def gen(A,n,P,acc):
    if any(imap((lambda p:  allStar(p) and notNullOrZero(p,n)), P)):
       return []
    else:
       if n==0:
          return map(rev,[acc])
       else:
          aG=[]
          for a in A:
              aG += gen(A,n-1,advancePatterns(a,P),[a]+acc)
          return aG

##----------------------------