Re: [Haskell-cafe] DFAs and self-referential data

26 Dec 2010


      On Sun, 2010-12-26 at 13:58 +0200, Roman Cheplyaka wrote:
...
* Maxime Henrion  [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 :-).

Cheers,
Maxime