David Ritchie MacIver wrote:
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?
I have a solution that I like now, even though it involves quite a bit of code. Its core idea is very simple. The main ingredient is
data RegexpTrie a
which is a data type that represents an infinite trie-like structure, indexed by regular expressions. It comes with a lookup function,
lookupRE :: RegexpTrie a -> Regexp -> a
with the obvious semantics. It also provides a function to populate a trie,
populateRE :: (Regexp -> a) -> RegexpTrie a
With these functions we can build a map of *all* regular expressions to their corresponding FSM. This is where the knot-tying takes place:
fsm :: RegexpTrie FSM fsm = populateRE (\re -> State { transitions = Map.map (lookupRE fsm) (transitions' re) }
Finally, 'compile' becomes a trivial lookup,
compile :: Regexp -> FSM compile x = lookupRE fsm x
Detailed code can be found at http://hpaste.org/2341#a3 . enjoy, Bertram