Wednesday, May 27, 2009

Solutions to Chapter 8 (p. 212)

#1. For a fantastic discussion of implementing a simple regular-expression matcher, see the first chapter of Beautiful Code -- probably the most beautiful chapter of that whole book. And as for the solution:

matchesGlob2 :: FilePath -> String -> Bool
matchesGlob2 fp "" = null fp
matchesGlob2 (c:fp) ('?':pat) = matchesGlob2 fp pat
matchesGlob2 fp ('*':pat) = matchStar fp pat
matchesGlob2 fp ('[':pat) = matchCharClass fp pat
matchesGlob2 (c:fp) (p:pat) = (c == p) && matchesGlob2 fp pat
matchesGlob2 "" _ = False

matchCharClass :: FilePath -> String -> Bool
 -- string is list of chars to match ++ "]" ++ rest of pattern.
 -- if starts with "!", negate meaning.
matchCharClass _ pat | not (']' `elem` pat) = error "Unmatched '['"
matchCharClass (c:fp) ('!':pat) = (c `notElem` (getCharClass pat)) && matchesGlob2 fp (afterCharClass pat)
matchCharClass (c:fp) pat = (c `elem` (getCharClass pat)) && matchesGlob2 fp (afterCharClass pat)

getCharClass :: String -> String
 -- assumes pat contains ']'
getCharClass pat = takeWhile (\x -> x /= ']') pat

afterCharClass :: String -> String
 -- assumes pat contains ']'
afterCharClass pat = tail $ dropWhile (\x -> x /= ']') pat  -- tail drops ']'

matchStar :: FilePath -> String -> Bool
matchStar "" pat = matchesGlob2 "" pat
matchStar fp pat = matchesGlob2 fp pat || matchStar (tail fp) pat

No comments:

Post a Comment