regex.hs

data RegEx a = Star (RegEx a)
             | Conc (RegEx a) (RegEx a)
             | Lit a
             | WildCard

match :: (Eq a,Show a) => [a] -> RegEx a -> Bool
match [x] (Lit y) = x == y -- 'a'    >>> 'a'
match _ (Lit _) = False    -- 'aaa'  >>> 'a'
match [x] WildCard = True  -- 'a'    >>> '.'
match _ WildCard = False   -- 'aaaa' >>> '.'
match [] (Star _) = True
match xs (Star r) = or $
  let l = length xs
  in [0..l] >>= \n ->
     let (prefix,suffix) = splitAt n xs
     in [match prefix r && match suffix (Star r)]
match xs (Conc r s) = or $ do
  let l = length xs
  n <- [0..l]
  let (prefix,suffix) = splitAt n xs
  [match prefix r && match suffix s]