Date: Wed, 7 Aug 2002 10:24:45 +1000 From: Andrew J Bromage <ajb@spamcop.net>
A large part of what I'm looking for at the moment is simply to find a fast and efficient way to express cyclic graphs in Haskell because in a present research project I need to manipulate machines with hundreds and thousands of states and my current, simple implementation simply won't do: my jobs balloon in size and die.
Using linear search to look up states is going to cause you prohibitively bad behaviour beyond 30 or so states no matter what you do. Some possibilities are: FGL (as previously mentioned), a dictionary structure like FiniteMap or clever use of IORefs.
OK, I guess I'll look into the FGL, FiniteMap and perhaps even (gasp) IORefs...
As a matter of interest, is all you are doing here converting regular expressions into DFAs? If so, a modern algorithm which doesn't go via NFAs might help a bit. I have some code if you would like it.
Thanks for offering. I'm actually not doing regexp -> nfa (although I do dfa -> regexp followed by rewrite simplification to get nice, textual representations of machines). I'm actually studying periodic orbits of a special class of operators on regular language space. Carl