[Haskell-cafe] DFAs and self-referential data

[Maxime Henrion]

On Sun, 2010-12-26 at 13:38 +0100, Maxime Henrion wrote:
> On Sun, 2010-12-26 at 13:58 +0200, Roman Cheplyaka wrote:
> > * Maxime Henrion <mhenrion at gmail.com> [2010-12-26 12:01:31+0100]
> > > Anyone knows what I'm doing wrong here?  I suspect my attempt at having
> > > self-referential data is somehow buggy; do I need to treat transitions
> > > to the same state differently?
> > 
> > The problem is that when you call 'self', you record *that* state of
> > your DFA in the map. When DFA gets updated further, the recorded
> > self-reference is not updated appropriately.
> > 
> > In your case a workaround is to call 'self' after all the other updates,
> > i.e.
> > 
> >     test :: String -> Bool
> >     test = accept s1
> >       where s1 = self '1' . path '0' s2 $ empty True
> >             s2 = self '1' . path '0' s1 $ empty False
> > 
> > But I don't see why you need 'self' at all -- you can just use path as
> > with any other type of transition:
> > 
> >     test :: String -> Bool
> >     test = accept s1
> >       where s1 = path '0' s2 . path '1' s1 $ empty True
> >             s2 = path '0' s1 . path '1' s2 $ empty False
> 
> Indeed this just works, thanks!  The reason I was using a 'self'
> function was that I initially thought it would be more convenient; I now
> see it doesn't, especially considering it doesn't even work.  However
> I'm a bit confused as to why things just work without having to reorder
> the calls when using the 'path' function - my brain seems to have
> difficulties following the code path here :-).

Oh, nevermind, I finally figured it out.  When using my 'self' function,
as you said, I point at the version of the DFA I have when calling
'self', and not the final version of the DFA after other calls to
'path'.  So as soon as I was following a self transition, I was ending
up with an 'old' version of the DFA.  Whereas in your version, the
binding I point to is the final DFA version.

Thanks a lot!

Maxime