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.

About these ads

Tags: bonsai, code, expression, Haskell, kata, match, praxis, programming, regular