regex

regex.hs

data Regex t
  = RegexLiteral t t
     --^ low and high, inclusive
  | RegexEmpty
  | RegexRejection
  | RegexUnion (Regex t) (Regex t)
  | RegexAppend (Regex t) (Regex t)
  | RegexStar (Regex t)

instance Semiring (Regex t) where                                                                                                              
  zero = RegexRejection                                                                                                                        
  RegexRejection `plus` y = y                                                                                                                  
  x `plus` RegexRejection = x                                                                                                                  
  RegexEmpty `plus` RegexEmpty = RegexEmpty                                                                                                    
  RegexEmpty `plus` RegexStar y = RegexStar y                                                                                                  
  RegexStar x `plus` RegexEmpty = RegexStar x                                                                                                  
  x `plus` y = RegexUnion x y                                                                                             
  one = RegexEmpty                                                                                                                             
  RegexEmpty `times` y = y                                                                                                                     
  x `times` RegexEmpty = x                                                                                                                     
  RegexRejection `times` _  = RegexRejection                                                                                                   
  _ `times` RegexRejection  = RegexRejection                                                                                                   
  x `times` y = RegexAppend x y                                                                                                                
                                                                                                                                               
instance Star (Regex t) where                                                                                                                  
  star RegexRejection = RegexEmpty                                                                                                             
  star RegexEmpty = RegexEmpty                                                                                                                 
  star (RegexStar x) = star x                                                                                                                  
  star x = star (RegexStar x)