Simple NFA-driven regexp engine.

NFA.hs

{-# LANGUAGE UnicodeSyntax #-}
module NFA
  ( single, (×), (⧺), star
  ) where

import Data.Maybe (fromMaybe, mapMaybe)
import Prelude hiding (concat)
import qualified Prelude

data NFA p = NFA { match ∷ (p → Maybe [p]) }

single ∷ Eq β ⇒ β → NFA [β]
single a = NFA $ go
  where go [] = Nothing
        go (x:xs)
          | a == x = Just [xs]
          | otherwise = Nothing 

(×) ∷ NFA β → NFA β → NFA β
(×) = concat

concat ∷ NFA β → NFA β → NFA β
concat μ ν = NFA $ \γ → do
  r ← match μ γ
  let ys = Prelude.concat $ mapMaybe (match ν) r
  if null ys
    then Nothing
    else Just $ ys

(⧺) ∷ NFA β → NFA β → NFA β
(⧺) = union

union ∷ NFA β → NFA β → NFA β
union μ ν = NFA $ \γ →
  let r = match μ γ
      s = match ν γ
      t = fromMaybe [] r ++ fromMaybe [] s
  in if null t then Nothing else Just t

star ∷ NFA β → NFA β
star μ = NFA $ Just . go
  where go xs = case match μ xs of
                  Just ys → xs : concatMap go ys 
                  Nothing → [xs]