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"
--
http://mail.python.org/mailman/listinfo/python-list
