Last time we wrote a parser for simple regular expressions. In today’s exercise, we have to write the matcher that checks if the input string matches the parsed regex. Since we wrote a similar matcher in the Beautiful Code exercise, this is mostly going to be a retread of that code. Still, let’s have a look.
A quick import:
This is the data structure we defined last time. Obviously we’re going to need it here again.
data Elem = Lit Char | Esc Char | Any | Set Bool [Elem] deriving Show data Chunk = Elem Elem | BoL | EoL | Star Elem deriving Show
matchElem is the only new function, because, since we now have two additional cases, it’s clearer to make a separate function out of it.
matchElem :: Elem -> Char -> Bool matchElem e c = case e of Lit l -> l == c Esc s -> show c == '\\':[s] Set b es -> b == any (`matchElem` c) es Any -> True
The other three functions have only received some small tweaks compared to the previous version. The logic remains unchanged.
matchHere :: [Chunk] -> String -> Bool matchHere (Elem r:rs) (x:xs) = matchElem r x && matchHere rs xs matchHere (Star e:r) xs = matchStar e r xs matchHere [EoL] xs = null xs matchHere r _ = null r matchStar :: Elem -> [Chunk] -> String -> Bool matchStar _ r xs | matchHere r xs = True matchStar e r (x:xs) = matchElem e x && matchStar e r xs matchStar _ _ _ = False match :: [Chunk] -> String -> Bool match (BoL:r) = matchHere r match r = any (matchHere r) . tails
A quick test shows everything working correctly:
main :: IO () main = do expect False [Elem digit, Star digit] expect True [BoL, Elem Any, Star Any, EoL] expect True hello expect True ([BoL, Star $ Lit ' '] ++ hello ++ [Star $ Lit ' ', EoL]) expect False [BoL, Elem $ Set False [Lit 'x'], Star Any, Elem digit, Star $ Lit ' ', Elem $ Lit 'x', EoL] where expect b cs = print $ match cs "hello" == b digit = Set True $ map Lit ['0'..'9'] hello = map (Elem . Lit) "hello"
Piece of cake.