Day 18 was all about the parsing, rather than the coding. It also meant going back to the original papers that prompted the development of attoparsec and other parsing libraries.
Data structures
This is about representing arithmetic expressions then evaluating them. As I didn't know what part 2 would bring, I thought I'd develop a data structure to hold a parsed expression, then evaluate it in a separate stage. It's just an algebraic type to hold the different operators. There's no need for a "bracket" option, as the final expression precedence is given by the shape of the Expression tree.
data Expression
= Number Integer
| Mul Expression Expression
| Add Expression Expression
deriving (Eq)
instance Show Expression where
show (Number x) = show x
show (Mul a b) = "(" ++ show a ++ " * " ++ show b ++ ")"
show (Add a b) = "(" ++ show a ++ " + " ++ show b ++ ")"
evaluate (Number x) = x
evaluate (Mul a b) = (evaluate a) * (evaluate b)
evaluate (Add a b) = (evaluate a) + (evaluate b)
(In my code, I decided not to use a custom Show instance, as I wanted to be clear what the parsers were generating.
First attempts
The parsing and association rules need to turn an expression like 1 + 2 * 3 + 4 into an Expression tree like this:
+
/ \
* 4
/ \
+ 3
/ \
1 2
A first attempt at parsing looked like this.
expressionP = mulExpression <|> addExpression
mulExpressionP = Mul <$> expressionP <* " * " *> elementP
addExpressionP = Add <$> expressionP <* " + " *> elementP
elementP = numberP <|> bracketedP
bracketedP = "(" *> exprP <* ")"
Which looks good, but fails instantly with an infinite loop. A little thought reveals why: the first + needs to be a few levels down in the tree. The parser needs to parse the whole expression in order to know how many levels down it needs to be. But the structure of the parser means it needs to make a decision now about this first +, before it's seen the rest of the expression. So it keeps creating more layers in the tree, hoping they'll be enough but never terminating.
Getting parsing working
This problem was solved in the original paper that introduced parser combinators. That paper illustrated the use of combinators with a calculator example, correctly parsing expressions like 1 + 2 + 3 into (1 + 2) + 3, which is what we want.
(Hutton, G., Meijer, E. (1998) “Monadic parsing in Haskell,” Journal of Functional Programming 8(4): 437–444).
The trick is to use the chainl1 combinator to chain, from the left, a bunch of operations. It's easier to use a more Applicative style for this combinator (Applicative hadn't been identified in 1998!), as described by Vibhav Sagar and Stephen Diehl. I'm slightly prefer Diehl's verison, so I'm using it here.
mulExprP = string " * " *> pure Mul
addExprP = string " + " *> pure Add
expessionrP = elementP `chainl1` (mulExprP <|> addExprP)
chainl1 :: Parser a -> Parser (a -> a -> a) -> Parser a
p `chainl1` op = do a <- p
rest a
where rest a = (do f <- op
b <- p
rest (f a b))
<|> return a
In this instance of the chainl1 parser, it first reads an element (a number or a bracketed term) and calls it a. If it can read the op (e.g. *), it combines a and the op with the result of parsing the rest of the input. If parsing rest fails, it just returns a.
That gives us the parse we want.
(chainl1 exists in the Text.ParserCombinators.ReadP library, but its somehow missing from attoparsec. But I'm using attoparsec now, so I'll just reimplement it.)
Given the ability to parse inputs, evaluating them is easy.
main =
do text <- TIO.readFile "data/advent18.txt"
print $ part1 text
part1 = parseAndEval expressionsP
parseAndEval parser text = sumEval $ successfulParse parser text
sumEval = sum . map evaluate
Introducing precedence
Using operator precedence takes my code closer to the original Functional Pearl, even if the precedence rules are reversed from convention. All that's needed are a couple of changes to the parser, and new names to avoid confusion.
pExpressionsP = pExprP `sepBy` endOfLine
pExprP = pTermP `chainl1` mulExprP
pTermP = pElementP `chainl1` addExprP
pElementP = numberP <|> pBracketedP
pBracketedP = "(" *> pExprP <* ")"
That's all that's needed!
Code
You can find the code here or on GitLab.