Simple NFA to DFA converter, following https://www.javatpoint.com/automata-conversion-from-nfa-to-dfa

nfa2dfa.hs

import qualified Data.Map.Strict as Map
import Control.Monad.Trans.State.Strict
import Control.Monad
import Control.Monad.Reader
import Data.Maybe (fromMaybe, maybeToList, isJust)
import Control.Applicative
import Data.Functor
import Data.Bifunctor (Bifunctor(bimap))
import Data.Bitraversable (bimapAccumL)
import qualified Data.Set as Set
import Control.Monad.Trans.Writer.Strict
type StateIndex = Int
type Token = Char
type DFAState = Set.Set StateIndex
type NFATable = Map.Map StateIndex (Map.Map Token [StateIndex])
type DFATable = Map.Map DFAState (Map.Map Token DFAState)

nfaEdgesFrom :: StateIndex -> NFATable -> Map.Map Token [StateIndex]
nfaEdgesFrom s t = fromMaybe Map.empty (Map.lookup s t)

getDfaEdges :: DFAState -> NFATable -> Map.Map Token DFAState
getDfaEdges ss t =
        let es  = map (`nfaEdgesFrom` t) (Set.toList ss)
            es' = Map.unionsWith (++) es
        in Map.map Set.fromList es'

writeTableM :: (Ord k) => (k -> (v, [k])) -> k -> State (Map.Map k v) ()
writeTableM f k = do
    modify $ Map.insert k v
    mapM_ inner ks'
    where
        (v, ks') = f k
        inner k' = do
            existing <- gets $ Map.lookup k'
            unless (isJust existing) $ writeTableM f k'

makeDfaRow :: NFATable -> DFAState -> (Map.Map Token DFAState, [DFAState])
makeDfaRow t s =
    let es = getDfaEdges s t
    in (es, map snd $ Map.toList es)

determinize :: StateIndex -> NFATable -> DFATable
determinize s nfa = execState inner Map.empty
    where
        inner = writeTableM (makeDfaRow nfa) $ Set.fromList [s]

exampleNfa :: NFATable
exampleNfa = Map.fromList [
        (0, Map.fromList [
                ('0', [0]),
                ('1', [1])]),
        (1, Map.fromList [
                ('0', [1, 2]),
                ('1', [1])]),
        (2, Map.fromList [
                ('0', [2]),
                ('1', [1, 2])])
    ]

exampleOut = determinize 0 exampleNfa