Minimal Purely Applicative Parser

Question

I'm trying to figure out how to build a "purely applicative parser" based on a simple parser implementation. The parser would not use monads in its implementation. I asked this question previously but mis-framed it so I'm trying again.

Here is the basic type and its Functor, Applicative and Alternative implementations:

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

instance Functor Parser where
  fmap f (Parser cs) = Parser (\s -> [(f a, b) | (a, b) <- cs s])

instance Applicative Parser where
  pure = Parser (\s -> [(a,s)])
  (Parser cs1) <*> (Parser cs2) = Parser (\s -> [(f a, s2) | (f, s1) <- cs1 s, (a, s2) <- cs2 s1])

instance Alternative Parser where
  empty = Parser $ \s -> []
  p <|> q = Parser $ \s ->
    case parse p s of
      [] -> parse q s
      r  -> r

The item function takes a character off the stream:

item :: Parser Char
item = Parser $ \s ->
  case s of
   [] -> []
   (c:cs) -> [(c,cs)]

At this point, I want to implement digit. I can of course do this:

digit = Parser $ \s ->
  case s of
    [] -> []
    (c:cs) -> if isDigit c then [(c, cs)] else []

but I'm replicating the code of item. I'd like to implement digit based on item.

How do I go about implementing digit, using item to take a character off the stream and then checking to see if the character is a digit without bringing monadic concepts into the implementation?

Answer 1

Functors allow you to act on somethings values. For example, if you have a list [1,2,3], you can change the contents. Note that Functors do not allow changing structure. map can not change the length of a list.

Applicatives allow you to combine structure, and the content is mushed together somehow. But the values can not change influence the structure.

Namely, given an item, we can change its structure, and we can change its content, but the content can not change the structure. We can't choose to fail on some content and not other.

If anyone knows how to state this more formally and provably, I'm all ears (it probably has to do with free theorems).

Answer 2

First, let us write down all the tools we currently have at hand:

-- Data constructor
Parser :: (String -> [(a, String)]) -> Parser a

-- field accessor
parse :: Parser a -> String -> [(a, String)]

-- instances, replace 'f' by 'Parser'
fmap  :: Functor f     =>   (a -> b) -> f a -> f b
(<*>) :: Applicative f => f (a -> b) -> f a -> f b
pure  :: Applicative f =>                 a -> f a

-- the parser at hand
item :: Parser Char

-- the parser we want to write with item
digit :: Parser Char
digit = magic item

-- ?
magic :: Parser Char -> Parser Char

The real question at hand is "what is magic"? There are only so many things we can use. Its type indicates fmap, but we can rule that out. All we can provide is some function a -> b, but there is no f :: Char -> Char that makes fmap f indicate a failure.

What about (<*>), can this help? Well, again, the answer is no. The only thing we can do here is to take the (a -> b) out of the context and apply it; whatever that means in the context of the given Applicative. We can rule pure out.

The problem is that we need to check the Char that item might parse and change the context. We need something like Char -> Parser Char

But we didn't rule Parser or parse out!

magic p = Parser $ \s ->
  case parse p s of -- < item will be used here
    [(c, cs)] -> if isDigit c then [(c, cs)] else []
    _         -> []

Yes, I know, it's duplicate code, but now it's using item. It's using item before inspecting the character. That's the only way we can use item here. And now, there is some kind of sequence implied: item has to succeed before digit can do it's work.

Alternatively, we could have tried this way:

digit' c :: Char -> Parser Char
digit' c = if isDigit c then pure c else empty

But then fmap digit' item would have the type Parser (Parser Char), which can only get collapsed with a join-like function. That's why monads are more powerful than applicative.

That being said, you can get around all of the monad requirements if you use a more general function first:

satisfy :: (Char -> Bool) -> Parser Char
satisfy = Parser $ \s -> 
   case s of
     (c:cs) | p c -> [(c, cs)]
     _            -> []

You can then define both item and digit in terms of satisfy:

item  = satisfy (const True)
digit = satisfy isDigit

That way digit does not have to inspect the result of a previous parser.