Better Applicative instance for Parser (Haskell)

Question

I'm working through the Brent Yorgey Haskell course, and I'm having trouble defining a good instance for Applicative. A parser is defined as follows:

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

The function takes a string, parses a certain amount of input, and returns a Maybe tuple where the first value is the type of the parser, and the rest is the unparsed remainder of the string. For example, this is a parser for positive integers:

posInt :: Parser Integer
posInt = Parser f
  where
    f xs
      | null ns   = Nothing
      | otherwise = Just (read ns, rest)
      where (ns, rest) = span isDigit xs

The assignment is to make an Applicative instance for Parser. We start with a Functor instance (which is relatively straight-forward, I think):

first :: (a -> b) -> (a,c) -> (b,c)
first f (a, c) = (f a, c)

instance Functor Parser where
  fmap f p = Parser f' 
    where f' s = fmap (first f) $ (runParser p) s

And then I tried my hand with Applicative:

collapse (Just (Just a)) = Just a
collapse _ = Nothing

extract (Just a, Just b) = Just (a,b)
extract _ = Nothing

appliedFunc :: Parser (a->b) -> Parser a -> String -> Maybe (b, String)
appliedFunc p1 p2 str = extract (f <*> fmap fst result2, fmap snd result2)
  where result1   = (runParser p1) str
        f         = fmap fst result1
        result2   = collapse $ fmap (runParser p2) $ fmap snd result1

instance Applicative Parser where
  pure a = Parser (\s -> Just (a, s))
  p1 <*> p2 = Parser (appliedFunc p1 p2)

...yuck. So my question is, how can I make my Applicative instance cleaner and less difficult to read? I feel like there's an easy answer for this question, but I haven't been able to wrap my head around the types just yet.

Answer 1

I assume you haven't got to Monads in the course yet. The way you are using collapse and fmap indicate to me that you are essentially reinventing Monads to solve this problem, and in particular the Monad Maybe instance. In fact your collapse is the same as join for this monad. And indeed using that is a very elegant way to solve this problem, but perhaps somewhat "cheating" at this point. The following is the best shape I could get it into while using your functions:

appliedFunc p1 p2 str = collapse $ fmap step1 (runParser p1 str)
  where
    step1 (f, str2) = collapse $ fmap step2 (runParser p2 str2)
      where
        step2 (x, str3) = Just (f x, str3)

Once you get to Monads proper, you should be able to rewrite this with the even more succinct (>>=) operator and/or do notation.

Another alternative which is almost as simple, but doesn't require reinventing monads, is to use explicit pattern matching of the Maybes. Then you can get something like:

appliedFunc p1 p2 str = case runParser p1 str of
    Nothing        -> Nothing
    Just (f, str2) -> case runParser p2 str2 of
        Nothing        -> Nothing
        Just (x, str3) -> Just (f x, str3)

Answer 2

This is probably not what you want, but I wanted to mention in passing that there is a really succinct way to implement this:

{-# LANGUAGE GeneralizedNewtypeDeriving #-}

import Control.Applicative
import Control.Monad.Trans.State

newtype Parser a = Parser { unParser :: StateT String Maybe a }
    deriving (Functor, Applicative, Monad, Alternative)

runParser :: Parser a -> String -> Maybe (a, String)
runParser = runStateT . unParser

parser :: (String -> Maybe (a, String)) -> Parser a
parser = Parser . StateT

The reason this works is that under the hood StateT is implemented as:

newtype StateT s m a = StateT { runStateT :: s -> m (a, s) }

If you specialize s to String and specialize m to Maybe, you get:

StateT String Maybe a  ~  String -> Maybe (a, String)

... which is the same as your type.

StateT has the following instances provided automatically for you:

instance Monad m => Functor     (StateT s m)
instance Monad m => Applicative (StateT s m)
instance Monad m => Monad       (StateT s m)

instance Alternative m => Alternative (StateT s m)

... and we can specialize m in those instances to Maybe because Maybe implements both Alternative and Monad:

instance Monad Maybe

instance Alternative Maybe

... so that means that StateT s Maybe is automatically a Functor, Applicative, Monad and Alternative without any additional work on our part.

The last part of the trick is GeneralizedNewtypeDeriving, which lets us lift type class instances through a newtype wrapper. Since our underlying StateT type is a Functor, Applicative, Monad, and Alternative, we can automatically lift all four type class instances through our newtype by adding:

... deriving (Functor, Applicative, Monad, Alternative)

... and the compiler will reimplement them for our newtype, taking care to do all the newtype wrapping and unwrapping for us.

So if you want to figure out how to implement Applicative for your parser, you may want to study how Applicative is implemented for StateT and then deduce from that how to implement it for your parser type.