Efficiency of list indices in definitions

[Andrew J Bromage]

G'day all.

On Tue, Aug 06, 2002 at 01:00:36PM -0600, Carl McTague wrote:

> 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.

> At the same time, code
> written and run in the early eighties outperforms mine!!  (Blushing
> with shame.)  Basically, I'm trying to find out whether Haskell is
> inherently that much slower or whether I am simply not yet quite
> competent enough to approach the problem correctly.

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.

Cheers,
Andrew Bromage