Identity parser

As an exercise¹, I've written a string parser that only uses char parsers and Trifecta:

import           Text.Trifecta
import           Control.Applicative            ( pure )

stringParserWithChar :: String -> Parser Char
stringParserWithChar stringToParse =
  foldr (\c otherParser -> otherParser >> char c) identityParser
    $ reverse stringToParse
  where identityParser = pure '?' -- ← This works but I think I can do better

The parser does its job just fine:

parseString (stringParserWithChar "123") mempty "1234"
-- Yields: Success '3'

Yet, I'm not happy with the specific identityParser to which I applied foldr. It seems hacky to have to choose an arbitrary character for pure.

My first intuition was to use mempty but Parser is not a monoid. It is an applicative but empty constitutes an unsuccessful parser².

What I'm looking for instead is a parser that works as a neutral element when combined with other parsers. It should successfully do nothing, i.e., not advance the cursor and let the next parser consume the character.

Is there an identity parser as described above in Trifecta or in another library? Or are parsers not meant to be used in a fold?

¹ The exercise is from the parser combinators chapter of the book Haskell Programming from first principles.

² As helpfully pointed out by cole, Parser is an Alternative and thus a monoid. The empty function stems from Alternative, not Parser's applicative instance.

Solution

Don't you want this to parse a String? Right now, as you can tell from the function signature, it parses a Char, returning the last character. Just because you only have a Char parser doesn't mean you can't make a String parser.

I'm going to assume that you want to parse a string, in which case your base case is simple: your identityParser is just pure "".

I think something like this should work (and it should be in the right order but might be reversed).

stringParserWithChar :: String -> Parser String
stringParserWithChar = traverse char

Unrolled, you get something like

stringParserWithChar' :: String -> Parser String
stringParserWithChar' "" = pure ""
stringParserWithChar' (c:cs) = liftA2 (:) (char c) (stringParserWithChar' cs)
-- the above with do notation, note that you can also just sequence the results of
-- 'char c' and 'stringParserWithChar' cs' and instead just return 'pure (c:cs)'
-- stringParserWithChar' (c:cs) = do
--   c'  <- char c
--   cs' <- stringParserWithChar' cs
--   pure (c':cs')

Let me know if they don't work since I can't test them right now…

A digression on monoids

My first intuition was to use mempty but Parser is not a monoid.

Ah, but that is not quite the case. Parser is an Alternative, which is a Monoid. But you don't really need to look at the Alt typeclass of Data.Monoid to understand this; Alternative's typeclass definition looks just like a Monoid's:

class Applicative f => Alternative f where
  empty :: f a
  (<|>) :: f a -> f a -> f a
  -- more definitions...

class Semigroup a => Monoid a where
  mempty  :: a
  mappend :: a -> a -> a
  -- more definitions...

Unfortunately, you want something that acts more like a product instead of an Alt, but that's what the default behavior of Parser does.