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
instance Monad Parser where
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.
Monad,Applicative, andFunctor, and write your parser more concise. \$\endgroup\$