Programming challenge: wildcard exclusion in cartesian products

[Dan Piponi]

Is this Haskell implementation what you want? It does the wildcard
matching through a state machine and it essentially threads the
state machine through the cartesian product, switching to the
ordinary cartesian product when possible as an optimisation.
The execution of the state machine is shared by strings with the
same prefix making it reasonably efficient even though the state
machine itself isn't optimised.

If it doesn't work, I'm sure it's only a few typos away...

-- generate strings of length n from alphabet l such that
-- the state machine, with transition function t, is not on
-- a final state (determined by function f) at the
-- end of the string.
-- If the state is ever 'unmatchable' (as determined by u)
-- we just return the cartesian product as no rejection
-- can take place.
generate f u t s 0 l = if f s then [] else [[]]
generate f u t s n l | u s = sequence (replicate n l)
                     | otherwise =
                     [a:b | a <- l, let s' = t s a,
                        b <- generate f u t s' (n-1) l]

-- The states are lists of regular expressions
-- where [a,b,..] means match a or b or...

-- This is the transition function for our machine.
transition pat a = pat >>= d a where
    -- Brzozowski derivative
    d a [] = []
    d a p@('*':pat) = p:d a pat
    d a (p:pat) | a==p = [pat]
                | otherwise = []

-- A terminal state is one that matches the null string
terminal p = or $ map terminal' p where
    terminal' "" = True
    terminal' ('*':p) = terminal' p
    terminal' _ = False

run n alphabet pat =
        generate terminal null transition [pat] n alphabet

test = run 3 "abc" "aa*a"