# [Haskell-cafe] DFAs and self-referential data

Maxime Henrion mhenrion at gmail.com
Sun Dec 26 12:01:31 CET 2010

```	Hello all,

I've been playing with some code to work with DFAs, but I'm now faced
with an implementation problem.  In order to have states that can
transition to themselves, it seems I would need self-referential data;
otherwise I would need to separate those transitions from the rest and
handle them specially in the code.  I tried to exploit laziness in order
to get self-referential data as shown in the 'self' function below:

module DFA where

import Data.Map (Map)
import qualified Data.Map as M

data DFA a =
DFA
(Map a (DFA a))     -- The set of transitions functions
Bool                -- Is this a final state?

accept :: Ord a => DFA a -> [a] -> Bool
accept (DFA _ f)  []     = f
accept (DFA ts f) (x:xs) = maybe False (`accept` xs) (M.lookup x
ts)

empty :: Bool -> DFA a
empty = DFA M.empty

path :: Ord a => a -> DFA a -> DFA a -> DFA a
path x d' (DFA ts f) = DFA (M.insert x d' ts) f

self :: Ord a => a -> DFA a -> DFA a
self x d = let d' = path x d' d in d'

test :: String -> Bool
test = accept s1
where s1 = path '0' s2 . self '1' \$ empty True
s2 = path '0' s1 . self '1' \$ empty False

The automaton I construct in the 'test' function is the example one from
(http://en.wikipedia.org/wiki/Deterministic_finite_automaton) on DFAs.
It should accept any string formed with ones and zeros that contain an
even number of zeros (or, equivalently, strings that match the regular
expression "1*(0(1*)0(1*))*").

Unfortunately, this doesn't seem to give the desired effect:

*DFA> test "0"
False
*DFA> test "00"
True
*DFA> test "000"
False
*DFA> test "0000"
True
*DFA> test "1"
True
*DFA> test "11"
True
*DFA> test "111"
True
*DFA> test "11100"
False

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?

Cheers,
Maxime

```