I'm very new to haskell (I never used Monads, Functors and other things) and FP in general. I decided to write the simplest parser I possibly can with some expansion possibilities. (I have a general interest in programming languages, so this is why I chose to do this...).

I have a simple parser type:

type Parser a = String -> (Maybe a, String)
-- (Nothing, ErrorMessage)
-- (Just a, Leftovers)


I can parse any character and return an error if there are none:

eatParser :: Parser Char
eatParser []     = (Nothing, "Unexpected EOF")
eatParser (x:xs) = (Just x, xs)


I can parse a specific character:

charParser :: Char -> Parser Char
charParser c s = case eatParser s of
(Nothing, e) -> (Nothing, e)
(Just x, xs) | x == c -> (Just x, xs)
(Just x, _) | x /= c ->
(Nothing,
"Expected " ++ [c] ++ ", but got " ++ [x] ++ " instead.")


Also, a specific string:

stringParser :: String -> Parser String
stringParser [] s = (Just "", s)
stringParser u s = case charParser (head u) s of
(Nothing, e) -> (Nothing, e)
(Just x, xs) -> case stringParser (tail u) xs of
(Nothing, e) -> (Nothing, e)
(Just x', xs') -> (Just $x : x', xs')  And any word: varParser :: Parser String varParser s = case eatParser s of (Nothing, _) -> (Just [], []) (Just x, xs) | not$ isLetter x -> (Just [], xs)
(Just x, xs) | isLetter x ->
case varParser xs of
(Nothing, e') -> (Nothing, e')
(Just [], _) -> (Just [x], xs)
(Just x', xs') ->
(Just $x : x', xs')  And finally, the expression parser data Expr = Open Expr | Value String deriving (Show) exprParser :: Parser Expr exprParser s = case charParser '(' s of (Nothing, _) -> case varParser s of (Nothing, e) -> (Nothing, e) (Just x, xs) -> (Just$ Value x, xs)
(Just _, xs) -> case exprParser xs of
(Nothing, e)  -> (Nothing, e)
(Just q, xs') -> case charParser ')' xs' of
(Nothing, e)   -> (Nothing, e)
(Just _, xs'') -> (Just $Open q, xs'')  Here are some examples of what the code does:  *Test2> eatParser "abc" (Just 'a',"bc") *Test2> charParser 'a' "abc" (Just 'a',"bc") *Test2> charParser 'b' "abc" (Nothing,"Expected b, but got a instead.") *Test2> stringParser "abc" "abce" (Just "abc","e") *Test2> stringParser "abc" "abc" (Just "abc","") *Test2> stringParser "abc" "axbc" (Nothing,"Expected b, but got x instead.") *Test2> varParser "abc" (Just "abc","") *Test2> varParser "abc2" (Just "abc","2") *Test2> varParser "abc abc2" (Just "abc"," abc2") *Test2> exprParser "((aa))bc" (Just (Open (Open (Value "aa"))),"bc") *Test2> exprParser "((aa)b)bc)" (Nothing,"Expected ), but got b instead.")  I know that there is a way to simplify all of the case ... s of (Nothing, e) -> (Nothing, e) (Just x, xs) -> ... And not use parserSequence... Can you tell what I can improve? Thanks in advance :D • You're on a right track! I can't comment too much right now, but I would suggest checking out one of the following resources: * cs.nott.ac.uk/~pszgmh/monparsing.pdf * youtu.be/N9RUqGYuGfw The first one is more complete imo, and it is also "the" original paper on this topic, afaik. Dec 15 '20 at 11:28 • I think what you can improve is to learn Monad, Applicative, and Functor, and write your parser more concise. Dec 16 '20 at 4:45 • I'm trying to now :D I'll make an update with those in mind when I learn them! Dec 16 '20 at 9:45 ## 1 Answer ### Short Answer This looks like a decent attempt. There are a few minor stylistic issues, but I think the biggest conceptual problem is a bad choice of Parser type. You should separate ErrorMessage from Leftovers, as these aren't the same sort of thing and so shouldn't share a single field in the algebraic type. Much clearer is: type Parser a = String -> Either Error (Maybe a, String) type Error = String  You've acknowledged that you've never used monads and functors. Well, there's no time like the present! Parsers and monads are a match made in heaven. With the cost of some gnarly monad boilerplate, you can rewrite the bulk of your parsing logic in a much cleaner style, as I show below. Since you have an interest in programming languages and parsing anyway, I'd suggest reading through some tutorials that show how to write monadic parsers from scratch. It's a great way to start using monads. See this article or this blog post for example. These and other older resources are based on the old version of the Monad class, and you'll get error messages about missing Applicative or Alternative instances. You can see the notes in the 7.10.x migration guide for how to fix old code so it compiles. ### Long Answer If you want to write a non-monadic parser, this looks like a reasonable first attempt. A few minor stylistic points. When writing two guards for the same pattern (or compatible patterns), like here: case ... of (Just x, xs) | x == c -> ... (Just x, _) | x /= c -> ...  it's more usual to chain the guards without repeating the pattern: case ... of (Just x, xs) | x == c -> ... | x /= c -> ...  Also, if you have two mutually exclusive guards, it's more usual to use otherwise than write a negated form of the guard. So, charParser would be written: charParser :: Char -> Parser Char charParser c s = case eatParser s of (Nothing, e) -> (Nothing, e) (Just x, xs) | x == c -> (Just x, xs) | otherwise -> (Nothing, "...")  This has a further advantage that if you turn on the ghc -Wall flag, it'll warn you about case statements and function definitions that don't cover all possible patterns, but mutually exclusive guards will generate false positives unless you use otherwise. (That is, the compiler isn't willing to assume that it's impossible for both x == c and x /= c to fail.) Also, this is more personal preference, but I think it makes more sense to make the "success" case more prominent by moving it to the front: charParser :: Char -> Parser Char charParser c s = case eatParser s of (Just x, xs) | x == c -> (Just x, xs) -- we succeed | otherwise -> (Nothing, "...") -- or experience various... (Nothing, e) -> (Nothing, e) -- ...types of failure  It's a big newbie mistake to write functions with lots of head and tail calls. Pattern matching with x:xs is preferred, since it's not only clearer, but if you turn on -Wall and stamp out any warnings, the pattern matching code is guaranteed not to try to take the head or tail of an empty list. You've done a good job of using patterns instead of head and tail, but I'd extend this to stringParser, too: stringParser :: String -> Parser String stringParser [] s = (Just "", s) stringParser (u:us) s = case charParser u s of (Just x, xs) -> case stringParser us xs of (Just x', xs') -> (Just$ x : x', xs')
(Nothing, e) -> (Nothing, e)
(Nothing, e) -> (Nothing, e)


The use of x' here is confusing though, since I'd expect it to have the same type as x, but x :: Char and x' :: String have different types. I guess I'd rename the variables to more consistently identify the "rest" of the stream and differentiate it from what we're trying to parse u:us and what we've actually parsed x:xs:

stringParser :: String -> Parser String
stringParser [] s = (Just "", s)
stringParser (u:us) s = case charParser u s of
(Just x, rest) -> case stringParser us rest of
(Just xs, rest') -> (Just (x:xs), rest')
(Nothing, e) -> (Nothing, e)
(Nothing, e) -> (Nothing, e)


I think this makes the function a little clearer. Technically, x:xs isn't needed since it's just a copy of u:us, so you could write:

stringParser :: String -> Parser String
stringParser [] s = (Just "", s)
stringParser (u:us) s = case charParser u s of
(Just _, rest) -> case stringParser us rest of
(Just _, rest') -> (Just (u:us), rest')
(Nothing, e) -> (Nothing, e)
(Nothing, e) -> (Nothing, e)


Some people think it's important to preserve the value u:us for return with @-syntax:

stringParser :: String -> Parser String
stringParser [] s = (Just "", s)
stringParser uall@(u:us) s = case charParser u s of
(Just _, rest) -> case stringParser us rest of
(Just _, rest') -> (Just uall, rest')   -- we return "uall" here
(Nothing, e) -> (Nothing, e)
(Nothing, e) -> (Nothing, e)


I don't know if this is clearer, and the @-syntax is pretty repulsive. I think there's a misguided notion that there's a performance gain here by not re-creating the u:us value right after breaking it apart, but GHC optimizes it and produces equivalent code, so use whichever is clearer.

There seems to be a bug in varParser. In the case with not (isLetter x), the x token is thrown away, so the following test fails:

> varParser "123"
(Just "","23")


This should either return (Just "", "123") or (Nothing, "expected a letter"), I guess. You don't notice this bug because the recursive call of varParser compensates for it through an extra case. If you fix it, then that case becomes redundant and the EOF case can be merged with the not-a-letter case, so you can simplify varParser to something more like:

varParser :: Parser String
varParser s = case eatParser s of
(Just x, rest) | isLetter x -> case varParser rest of
(Just xs, rest') -> (Just (x:xs), rest')
(Nothing, e) -> (Nothing, e)
_ -> (Just [], s)


Technically, the (Nothing, e) case can never be triggered, but you need to keep it in to avoid a -Wall warning.

There are two "big ticket" problems with your code, however. The first is that your choice of Parser data type is poor:

type Parser a = String -> (Maybe a, String)


In the return type here, you use the first Maybe a component as a flag: if it's Nothing, the second String component is an error. If it's Just a, the second String component is the rest of the stream. However, parse errors and rest-of-streams are not semantically comparable things, and it's pure coincidence that they happen to have the same String type, so they shouldn't be represented by the same field in your algebraic type. From a practical standpoint, if you decided to refactor your code to parse streams of tokens other than Strings or use a different Error type that includes location information, you'll have to do a lot of unnecessary modification. You also introduce the potential for dumb programming bugs, where you start parsing error message or printing stream remainders on the console, because they're both String and the bad code will type check. But these practical concerns are probably not that convincing, and in this simple example probably aren't too serious. It's really just the theoretical, best-practices issue that this is a bad design when a much more straightforward and idiomatic type is available:

type Parser a = String -> Either String (a, String)


Most Haskell programmers would be confused by your Parser type. But, every Haskell programmer will understand this new Parser type immediately. The Either error result convention and the String -> (a, String) pattern, and the combination of the two of them, are hardwired into their brains. You could make it even more obvious by writing:

type Parser a = String -> Either Error (a, String)
type Error = String


Anyway, the resulting rewritten parsers look about the same, for example:

charParser :: Char -> Parser Char
charParser c s = case eatParser s of
Right (x, xs) | x == c -> Right (x, xs)
| otherwise -> Left $"Expected " ++ [c] ++ ", but got " ++ [x] ++ " instead." Left e -> Left e  but I think this new parser type is just a fundamentally better choice. The second big ticket problem with your code is, as you've acknowledged in the question, the proliferation of nested cases to handle cascading parse failure. In many types of code, error handling involves handling exceptional situations, and you can usually get away with no more than a few deeply nested cases where the overall "success path" remains clear. In parsing, failure of parsers is fundamental to the parsing process, and nearly every parser ends up handling multiple failure modes, often (as in your varParser) in ways that involve converting "failure" into "success" or vice versa. The best way to fix this is to introduce parser combinators. The combinators themselves can use ugly nested cases in their implementation, but if the combinators have "meaning", they will result in code that's easier to read where it matters. For example, you could introduce a combinator like: combine :: (a -> b -> c) -> Parser a -> Parser b -> Parser c combine f p q s = case p s of Right (x, s') -> case q s' of Right (y, s'') -> Right (f x y, s'') Left e -> Left e Left e -> Left e  Here combine applies two parsers in sequence and -- if they both succeed -- uses a function to combine their results. With this combinator, you can rewrite stringParser as: stringParser :: String -> Parser String stringParser "" s = Right ("", s) stringParser (u:us) s = combine (:) (charParser u) (stringParser us) s  A satisfy combinator that applies a parser and ensures the result satifies a condition: satisfy :: (a -> Bool) -> String -> Parser a -> Parser a satisfy f unexpected p s = case p s of Right (x, rest) | f x -> Right (x, rest) | otherwise -> Left unexpected  let's you rewrite charParser as: charParser :: Char -> Parser Char charParser c = satisfy (==c) unexpected eatParser where unexpected x = "Expected " ++ [c] ++ ", but got " ++ [x] ++ " instead."  These combinators end up being of limited use because not a lot of thought has gone into them. For example, if you try to rewrite varParser using them, you might try something like: varParser :: Parser String varParser s = combine (:) (satisfy isLetter unexpected eatParser) varParser s where unexpected x = "Expected a letter, but got " ++ [x] ++ " instead."  but this won't work because the first non-letter character throws an error instead of ending the variable name. This is why it's worth learning how to use monads for parsers. A monad is a good fit for the problem of combining parsers together, and it provides a whole host of pre-written combinators that work with any monadic parser. The combinators have been thoughtfully designed, and you rarely find yourself in the situation where you need to write a combinator from scratch, because you can almost always find one that does what you want. Anyway, my rewrite of your parser without any combinators would look like this. It uses the Either-based parser type, reorders the nested cases to put "success" first, and cleans up some variable names and redundant cases: {-# OPTIONS_GHC -Wall #-} module MonadlessParser where import Data.Char type Parser a = String -> Either String (a, String) eatParser :: Parser Char eatParser [] = Left "Unexpected EOF" eatParser (x:rest) = Right (x, rest) charParser :: Char -> Parser Char charParser c s = case eatParser s of Right (x, rest) | x == c -> Right (x, rest) | otherwise -> Left$ "Expected " ++ [c] ++
", but got " ++ [x] ++ " instead."
Left e -> Left e

stringParser :: String -> Parser String
stringParser [] s = Right ("", s)
stringParser (u:us) s = case charParser u s of
Right (_, rest) -> case stringParser us rest of
Right (_, rest') -> Right (u:us, rest')
Left e -> Left e
Left e -> Left e

varParser :: Parser String
varParser s = case eatParser s of
Right (x, rest)
| isLetter x -> case varParser rest of
Right (xs, rest') -> Right (x:xs, rest')
Left e -> Left e
_ -> Right ([], s)

data Expr = Open Expr | Value String deriving (Show, Eq)
exprParser :: Parser Expr
exprParser s = case charParser '(' s of
Right (_, rest) -> case exprParser rest of
Right (expr, rest') -> case charParser ')' rest' of
Right (_, rest'') -> Right (Open expr, rest'')
Left e -> Left e
Left e -> Left e
Left _ -> case varParser s of
Right (x, rest) -> Right (Value x, rest)
Left e -> Left e

main :: IO ()
main = do
print $eatParser "abc" == Right ('a',"bc") print$ charParser 'a' "abc" == Right ('a',"bc")
print $charParser 'b' "abc" == Left "Expected b, but got a instead." print$ stringParser "abc" "abce" == Right ("abc","e")
print $stringParser "abc" "abc" == Right ("abc","") print$ stringParser "abc" "axbc" == Left "Expected b, but got x instead."
print $varParser "abc" == Right ("abc","") print$ varParser "abc2" == Right ("abc","2")
print $varParser "abc abc2" == Right ("abc"," abc2") print$ exprParser "((aa))bc" == Right (Open (Open (Value "aa")),"bc")
print $exprParser "((aa)b)bc)" == Left "Expected ), but got b instead."  Writing a monadic version requires two difficult steps. First, you have to make your Parser a newtype and write Monad and related instance for it. This looks like black magic, but you eventually figure out how to do it reliably. Second, you need to learn about all the applicative and monadic combinators and how to use them. Once you've done that, the work you put in really pays off. Here's a full monadic version of your parser with comments that try to explain what's going on. Setting aside the ugly monadic instances, most of the parsers themselves are straightforward to write and understand. {-# LANGUAGE DeriveFunctor #-} {-# OPTIONS_GHC -Wall #-} module MonadParser where -- a bunch of combinators import Control.Applicative import Control.Applicative.Combinators import Control.Monad -- just for isLetter import Data.Char -- the hardest part, by far, is writing these instances newtype Parser a = Parser { runParser :: String -> Either String (a, String) } deriving (Functor) instance Applicative Parser where pure x = Parser$ \str -> Right (x, str)
(<*>) = ap
p >>= f = Parser $\str -> case runParser p str of Right (x, rest) -> case runParser (f x) rest of Right (y, rest') -> Right (y, rest') Left e -> Left e Left e -> Left e instance MonadFail Parser where fail err = Parser$ \_ -> Left err
instance Alternative Parser where
empty = fail "<empty>"
p <|> q = Parser $\str -> case runParser p str of Left _ -> runParser q str result -> result instance MonadPlus Parser -- we need to rewrite eatParser to use a Parser newtype eatParser :: Parser Char eatParser = Parser go where go (x:rest) = Right (x, rest) go [] = Left "unexpected EOF" -- a "satisfy" combinator is helpful; we have pre-written combinators for -- almost everything else satisfy :: (a -> Bool) -> Parser a -> Parser a satisfy f p = do x <- p guard (f x) return x -- now the hard word pays off... -- "satisfy" lets us easily write charParser charParser :: Char -> Parser Char charParser c = satisfy (==c) eatParser -- mapM runs charParser for each input character and puts the result -- together into a list of characters, namely the desired String stringParser :: String -> Parser String stringParser = mapM charParser -- this parses a single letter using Data.Char.isLetter letterParser :: Parser Char letterParser = satisfy isLetter eatParser -- some parses one or more of the given parser into a list (in this case, -- a list of characters, so a String) varParser :: Parser String varParser = some letterParser -- non-empty variable name -- the between combinator runs a parser between two other parsers; here -- parens p will run parser p between parentheses parens :: Parser a -> Parser a parens = between (charParser '(') (charParser ')') -- Here <$> just attaches the desired constructor to the return value
-- from the parsers.  The alternation operator <|> tries the first parser
-- and, if it fails, tries the second before giving up.
data Expr = Open Expr | Value String deriving (Show, Eq)
exprParser :: Parser Expr
exprParser = Open <$> parens exprParser <|> Value <$> varParser

-- All the tests still pass
main :: IO ()
main = do
print $runParser eatParser "abc" == Right ('a',"bc") print$ runParser (charParser 'a') "abc" == Right ('a',"bc")
print $runParser (charParser 'b') "abc" == Left "<empty>" print$ runParser (stringParser "abc") "abce" == Right ("abc","e")
print $runParser (stringParser "abc") "abc" == Right ("abc","") print$ runParser (stringParser "abc") "axbc" == Left "<empty>"
print $runParser varParser "abc" == Right ("abc","") print$ runParser varParser "abc2" == Right ("abc","2")
print $runParser varParser "abc abc2" == Right ("abc"," abc2") print$ runParser exprParser "((aa))bc" == Right (Open (Open (Value "aa")),"bc")
print \$ runParser exprParser "((aa)b)bc)" == Left "<empty>"


I hope that example whets your appetite for trying out monadic parsing.

• Wow! I didn't expect such a long and detailed answer! Thanks a lot! :D One thing that I didn't understand is what are MonadPlus and ap? I couldn't find anything on the internet :( Dec 17 '20 at 18:28
• MonadPlus is an historical artifact from when Monad wasn't also an Applicative. Nowadays, you probably don't need it for anything, but you get the instance for free if an Alternative instance is defined, so there's no harm in just automatically including it. The function ap is a default definition for <*> that works for anything with a Monad instance. It used to be useful on its own (for Monads that weren't Applicatives) but now it's really only useful for writing (<*>) = ap. Dec 17 '20 at 21:39
• Thank you for the explanation! :D Dec 18 '20 at 7:00