Skip to content

Instantly share code, notes, and snippets.

@shangaslammi
Created July 3, 2011 18:47
Show Gist options
  • Save shangaslammi/1062472 to your computer and use it in GitHub Desktop.
Save shangaslammi/1062472 to your computer and use it in GitHub Desktop.
Simple regexp matcher in Haskell
module Regex (match) where
import Data.List
data Token = C Char | Start | End deriving (Eq)
match :: String -> String -> Bool
match re = not . null . filter (not.null) . fmap match' . tails . tokenize
where match' = flip (foldl' (>>=)) (compile re) . return
tokenize = (Start:) . (++[End]) . map C
compile = reverse . foldl' go []
where go acc c = case c of
'*' -> star (head acc) : tail acc
'.' -> single (const True) : acc
'$' -> single (End==) : acc
'^' -> single (Start==) : acc
c -> single ((C c)==) : acc
single _ [] = []
single t (x:xs) = if t x then [xs] else []
star _ [] = [[]]
star m xs = xs : (m xs >>= star m)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment