## Programming Praxis – Regular Expressions, Part 2

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:

`import Data.List`

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.