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

[David Ritchie MacIver]

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