Parsing with Derivatives, via GADTs

Hammer.hs

data Parser a where
  Cat :: Parser a -> Parser b -> Parser (a, b)
  Alt :: Parser a -> Parser b -> Parser (Either a b)
  Rep :: Parser a -> Parser [a]
  Map :: Parser a -> (a -> b) -> Parser b
  Bnd :: Parser a -> (a -> Parser b) -> Parser b
  Lit :: Char -> Parser Char
  Ret :: [a] -> Parser a
  Nul :: Parser a
  Eps :: Parser a

instance Functor Parser where
  fmap = flip Map

instance Applicative Parser where
  pure = return
  (<*>) = ap

instance Alternative Parser where
  empty = Eps
  (<|>) = (fmap (either id id) .) . Alt
  many = Rep

instance Monad Parser where
  return = Ret . pure
  (>>=) = Bnd