module RegExS where

import Prelude hiding(seq)

type RegEx = String-> Maybe String

eps  :: RegEx 
char :: Char-> RegEx
arb  :: RegEx 
seq  :: RegEx-> RegEx-> RegEx
alt  :: RegEx-> RegEx-> RegEx
star :: RegEx-> RegEx
plus :: RegEx-> RegEx

eps s = Just s

chrp :: (Char-> Bool)-> RegEx
chrp p (i:is) | p i = Just is
chrp p rest         = Nothing

char c = chrp (c ==)

arb = chrp (const True)

seq re1 re2 str = re1 str >>= re2 

alt re1 re2 str = 
  -- Implement a longest-match selection (inefficient!)
  case (re1 str, re2 str) of  
    (Just r1, Just r2) -> Just $ if length r1 < length r2 then r1 else r2
    (Just r1, Nothing) -> Just r1
    (_, r2)            -> r2 

lst :: [RegEx]-> RegEx
lst = foldl seq eps  

str :: String-> RegEx
str = lst . map char

star re = alt (seq re (star re)) eps

plus re = seq re (star re)

