val it: α → α = fun

data MyState = Q0 | Q1 | Q2 | Q3 | Q4 deriving Show
data MyInput = I0 | I1 deriving Show

transition :: MyState -> MyInput -> (Bool, MyState)
transition Q0 I0 = (True, Q0)
transition Q0 I1 = (False, Q1)
transition Q1 I0 = (False, Q2)
transition Q1 I1 = (False, Q3)
transition Q2 I0 = (False, Q4)
transition Q2 I1 = (True, Q0)
transition Q3 I0 = (False, Q1)
transition Q3 I1 = (False, Q2)
transition Q4 I0 = (False, Q3)
transition Q4 I1 = (False, Q4)

dfa :: Bool -> [MyInput] -> State MyState Bool
dfa b [] = return b
dfa _ (i:is) = do s <- get
(b', s') <- return $ transition s i
put s'
dfa b' is

numToInput :: Integral a => a -> [MyInput]
numToInput n = reverse $ toInputList n
where toInputList :: Integral a => a -> [MyInput]
toInputList 0 = [I0]
toInputList 1 = [I1]
toInputList n =
if rem n 2 == 1 then I1 : toInputList (n `div` 2)
else I0 : toInputList (n `div` 2)

checkDFA :: Integral a => a -> Bool
checkDFA n = let (b, _) = checkMain Q0 in b
where checkMain :: MyState -> (Bool, MyState)
checkMain = runState (do b <- dfa False $ numToInput n
return b) > >ちと長いのは transition などの関数があるため。この DFA は、 0 または 1 を入力列として受け取り、その入力列を2進数とみなしたときに5の倍数であれば真となる DFA です。 > >二進数のリストを作るのは面倒なので、実際には数値から変換してますが。 > >*Main> map checkDFA [1..15]
[False,False,False,False,True,False,False,False,False,True,False,False,False,False,True] > >以上実行例。よしよし。ふむふむ。 >