instance Applicative Parser where
  pure a = Parser $ \s -> [(a, s)]
  (Parser ps) <*> (Parser qs) = Parser $ \s -> [ (f a, t)
                                               | (f, s') <- ps s
                                               , (a,t) <- qs s'
                                               ]

instance Alternative Parser where
  empty = Parser $ const []
  (Parser ps) <|> (Parser qs) = Parser $ (++) <$> ps <*> qs