Untitled

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)