NFAs

I saw this a while back and thought it was worth posting. Here’s a complete implementation of NFA (non-deterministic finite automata) in Haskell:

-- Specify the NFA data type
data NFA q s = NFA
{ intialState :: q
, isAccepting :: q -> Bool 
, transition :: q -> s -> [q]
}

-- Declare the type of the function test
NFA :: NFA q s -> [s] -> Bool
-- Actual function body test
NFA (NFA i a t) = any a . foldM t i

(Source)