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 _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe