[Haskell-cafe] "Tying the knot" with unknown keys

[Bertram Felgenhauer]

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