How do you chain an arbitrarily long series of atomic parsers using applicatives?

Question

Let's say I have this parser type:

newtype Parser a = Parser { runParser :: String -> Maybe (a, String) }

And this atomic parser unit:

satisfy :: ( Char -> Bool ) -> Parser Char
satisfy g = Parser $ \stream -> case stream of
    (x:xs) | g x -> Just ( x, xs )
    otherwise    -> Nothing

The parser implements these three interfaces:

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


instance Applicative Parser where
    pure a                      = Parser $ \xs0 -> Just ( a, xs0 )
    (Parser p1) <*> (Parser p2) = Parser $ \xs0 -> do
        (x1, xs1) <- p1 xs0
        (x2, xs2) <- p2 xs1
        return ( x1 x2, xs2 )

instance Alternative Parser where
    empty                        = Parser $ const Nothing
    (Parser p1) <|> (Parser p2)  = Parser $ \ss -> let ss1 = p1 ss in case ss1 of
        Nothing  -> p2 ss
        _        -> ss1

Now as I understand, I can now pop up to a higher level of abstraction and build more complex parsers by chaining satisfy using the applicative interface. In example:

-- | A parser that parses the first two chars in the stream if they are upper case
uParser = satisfy isUpper
parser1 = ( (:) <$> uParser ) <*> ( (\x -> [x]) <$> uParser )
runParser parser1 "HEllo" = Just ("HE","llo")
runParser parser1 "Hello" = Nothing

This is great, now what if I want to structure a computation such that the parser parses all cap letters in the stream until it encounters a lowercase letter? Use case:

runParser idealParser "hello"             = Nothing
runParser idealParser "HEllo"             = Just ("HE","llo")
runParser idealParser "HELLOIAMnotincaps" = Just ("HELLOIAM", "notincaps")

How do I express this notion of non-determined length?

Answer 1

Since you have an Alternative instance, you can simply use Control.Applicative.some to match a list of one or more occurrences.

> runParser (some uParser) "hello"
Nothing
> runParser (some uParser) "HEllo"
Just ("HE","llo")
> runParser (some uParser) "HELLOIAMnotincaps"
Just ("HELLOIAM","notincaps")

To implement it manually, you could use two mutually recursive parsers, e.g.

zeroOrMore = oneOrMore <|> pure []
oneOrMore  = (:) <$> uParser <*> zeroOrMore