Efficiency of list indices in definitions

[Carl McTague]

> 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