CODEWITHSUNDEEP
haskellparser-combinatorstrifecta
Matthias Braun
Matthias Braun

Reputation: 34423

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.

Upvotes: 1

Views: 313

Answers (2)

dfeuer
dfeuer

Reputation: 48631

Let's rewrite your fold+reverse into just a fold to clarify what's going on:

stringParserWithChar :: String -> Parser Char
stringParserWithChar =
  foldl (\otherParser c -> otherParser >> char c) identityParser
  where identityParser = pure '?'

Any time you see foldl used to build up something using its Monad instance, that's a bit suspicious[*]. It hints that you really want a monadic fold of some sort. Let's see here...

import Control.Monad

-- foldM :: (Foldable t, Monad m) => (b -> a -> m b) -> b -> t a -> m b
attempt1 :: String -> Parser Char
attempt1 = foldM _f _acc

This is going to run into the same sort of trouble you saw before: what can you use for a starting value? So let's use a standard trick and start with Maybe:

-- (Control.Monad.<=<)
--   :: Monad m => (b -> m c) -> (a -> m b) -> a -> m c
stringParserWithChar :: String -> Parser Char
stringParserWithChar =
  maybe empty pure <=< foldM _f _acc

Now we can start our fold off with Nothing, and immediately switch to Just and stay there. I'll let you fill in the blanks; GHC will helpfully show you their types.

[*] The main exception is when it's a "lazy monad" like Reader, lazy Writer, lazy State, etc. But parser monads are generally strict.

Upvotes: 1

cole
cole

Reputation: 725

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.

Upvotes: 2

Related Questions