I was playing with some code for compiling regular expressions to finite
state machines and I ran into the following problem. I've solved it, but
I'm not terribly happy with my solution and was wondering if someone
could come up with a better one. :-)
Essentially I have
data FSM = State { transitions :: (Map Char FSM) }
and
transitions' :: Regexp -> Map Char Regexp
I want to lift this so that the Regexps become states of the finite
state machine (while making sure I set up a loop in the data structure).
Tying the knot is the traditional way of doing such things, but we
couldn't figure out a way to make it work without the set of keys known
in advance because of the strictness of Map in its keys (an association
list was suggested, and that would probably work, but it seemed a bit
ugly and would be fairly inefficient).
In the end what I did was just work out the set of reachable regexps in
advance and use a standard tying the knot trick, but it felt vaguely
unsatisfactory (and does some repeat work which I felt should be
unneccessary). Anyone have a more elegant suggestion?
Regards,
David
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
