Efficiency of list indices in definitions

[Carl McTague]

Hi,

thanks for taking the time to consider my problem.

On Mon, Aug 05, 2002 at 07:12:12PM -0700, oleg@pobox.com wrote:
> To prevent such a behavior we ought to keep track of the states that
> we have already computed.

Yes, this is definitely an approach.  Perhaps it is the best one after
all, but I was interested in exploring the use of a recursive
datatype: I wonder how much faster and efficient it can make the
implementation (by avoiding linear searches through a state-label
association list.)

I also wonder whether this approach is so much different than the one
I described, once composed with finAuConsolidate.  I guess this is
really part of my question.  If so, then I prefer the finAuConsolidate
approach, since it extracts and generalizes the problem so that other
inductive algorithms may be coded up intuitively, then merely composed
with finAuConsolidate.

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

> (BTW, I had trouble with the automaton in the original article. That
> NFA recognized [1], which it should not). The acceptance function
> can be written as

I'm sorry, the automaton was right, the regexp wrong (in the sense
that it's a very important language in my work); it should be
(0(0+1))* + ((0+1)0)* I was just trying to simplify this and made a
mistake, I suppose I was aiming at 0*((0+1)0)*.

Thanks,
  Carl