Best applicative example for Parser (Haskell)

Question

I work through the Brent Yorgey Haskell course , and I am having trouble finding a good instance for Applicative. The 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 undisclosed 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 purpose is to create an applicative instance for Parser. We start with an instance of Functor (which, I think, is relatively straightforward):

 first :: (a -> b) -> (a,c) -> (b,c) first f (a, c) = (fa, c) instance Functor Parser where fmap fp = Parser f' where f' s = fmap (first f) $ (runParser p) s 

And then I tried my hand with Applied:

 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) 

... Ugh. So my question is: how can I make my application example cleaner and less difficult to read? I feel that there is an easy answer to this question, but so far I have not been able to circle my head around types.

Answer 1

I guess you haven't got to Monad yet. The way I use collapse and fmap tells me that you are basically reinventing Monad to solve this problem, and in particular for the Monad Maybe instance. Actually your collapse is the same as join for this monad. Indeed, using this is a very elegant way to solve this problem, but maybe a little "cheat" at this point. The following is the best form I could handle 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 (fx, str3) 

Once you get to the correct Monad , you can rewrite it with an even more concise statement (>>=) and / or do .

Another alternative, which is nearly as simple but does not require reuse of monads, is to use explicit pattern matching for Maybe s. 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 (fx, str3) 

Answer 2

This is probably not what you want, but I would like to mention in passing that there is a very concise 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 for this is that under the hood, StateT implemented as:

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

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

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

... which matches your type.

StateT following instances are automatically provided for you:

 instance Monad m => Functor (StateT sm) instance Monad m => Applicative (StateT sm) instance Monad m => Monad (StateT sm) instance Alternative m => Alternative (StateT sm) 

... and we can specialize m in these cases to Maybe , because Maybe implements both Alternative and Monad :

 instance Monad Maybe instance Alternative Maybe 

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

The last part of the trick is GeneralizedNewtypeDeriving , which allows us to remove instances of a type class through the newtype shell. Since our base type StateT is Functor , Applicative , Monad and Alternative , we can automatically raise all instances of a class class using our new type by adding:

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

... and the compiler will redefine them for our new type, taking care to do all the wrapping and deployment of the new type for us.

So, if you want to figure out how to implement Applicative for your parser, you can learn how Applicative implemented for StateT and then deduce from it how to implement it for your parser type.