import Control.Applicative

newtype Parser a = Parser { apply :: String -> [(a, String)] }

instance Functor Parser where
  fmap g (Parser p) = Parser $ \xs -> (map (\(x,y) -> (g x,y)) (p xs))

instance Applicative Parser where
  pure x = Parser $ \s -> [(x, s)]

  Parser pf <*> Parser px = Parser (\s -> [ (f x, sx) | (f, sf) <- pf $ s, (x, sx) <- px $ sf])


instance Alternative Parser where
  empty = Parser $ \_ -> []
  (Parser u) <|> (Parser v) = Parser (\s -> u s ++ v s)