-- Regular expression matching

-- Representation of regular expressions:
data RE a = Lit a
          | Alt  (RE a) (RE a)
          | Conc (RE a) (RE a)
          | Star (RE a)

plus :: RE a -> RE a
plus re = Conc re (Star re)

-- a|b|c
abcAlt :: RE Char
abcAlt = Alt (Lit 'a') (Alt (Lit 'b') (Lit 'c'))

-- abc
abc :: RE Char
abc = Conc (Lit 'a') (Conc (Lit 'b') (Lit 'c'))

-- ab*
abstar :: RE Char
abstar = Conc (Lit 'a') (Star (Lit 'b'))

-- ab+
abplus :: RE Char
abplus = Conc (Lit 'a') (plus (Lit 'b'))

-- The semantics of REs: sem re returns a possible word described by re
sem :: RE a -> [a]
sem (Lit c)    = [c]
sem (Alt a b)  = sem a ? sem b
sem (Conc a b) = sem a ++ sem b
sem (Star a)   = [] ? sem (Conc a (Star a))

-- Match a regular expression against a string:
match :: RE Char -> String -> Bool
match re s | sem re == s = True

-- Match a regular expression in a string:
grep :: RE Char -> String -> Bool
grep re s | _ ++ sem re ++ _ == s = True

-- Match a regular expression in a string and return the matching positions:
grepPos :: RE Char -> String -> (Int,Int)
grepPos re s | xs ++ sem re ++ ys == s = (length xs, length s - length ys)
  where xs,ys free