My Side Quest into Haskell, Reverse Polish Notation, and Parsing
26 Jun, 2025
My Journey into Haskell: Building a Reverse Polish Notation Calculator Introduction: A Side Quest
In my attempt to get my first paycheck, aka get a job, I have led myself down a fascinating rabbit hole into functional programming, mathematical notation, and parsing theory. This is the story of how I discovered Haskell, tackled reverse Polish notation, and learned about monadic parsing along the way.
My journey began when my friend Jackson Slipock encouraged me to explore functional programming. After a quick Google search, I landed on Haskell as my first functional language. Around the same time, during a networking call about job opportunities, someone mentioned reverse Polish notation. The idea struck me: why not build a reverse Polish notation calculator in Haskell?
What could have been a simple weekend project became weeks of deep learning. This blog chronicles that journey, drawing heavily from Graham Hutton's excellent book Programming in Haskell, which I highly recommend. What you're reading is my attempt to learn something deeply, implement it myself, and then teach it to others.
From Imperative to Functional: A Mental Shift
Coming from a background in Python and C—languages I'm comfortable with after a couple years of experience—Haskell represented a fundamental shift in thinking. Both Python and C are imperative languages that share similar concepts: loops, mutable data, global state, and variables that can be modified. The transition between them never required a major mental adjustment.
Functional programming throws all of that out the window.
In Haskell, functions are mathematical abstractions. Given the same input, a function will always produce the same output. There are no global variables, and data is immutable once created. Instead of writing a series of statements that accomplish a task, functional programming encourages building expressions that naturally compose together.
This is why Haskell has no loops. Instead, it pushes you to think recursively, building solutions through expressions that elegantly combine to produce results.
Why Choose Functional Programming?
The benefits became clear as I progressed: functional code tends to be more concise, easier to understand, and less prone to bugs. Haskell excels at representing complex ideas in just a few lines of code, and it makes translating mathematical concepts into working programs remarkably straightforward. As someone who majored in math and genuinely enjoys it, this felt incredibly satisfying.
These concepts might seem abstract at first—I certainly struggled with them initially. But they become clearer with practice, and keeping them in mind helps when encountering Haskell code for the first time. My first real "aha!" moment came when implementing merge sort, but before we get there, let's explore some things that were new to me as a first time functional programmer.
Recursive Types: Building Natural Numbers from Scratch
Let me start with a classic example that illustrates Haskell's elegance. Here's how you can define natural numbers (0, 1, 2, 3, 4...) recursively:
data Nat = Zero | Succ Nat
That's it. This simple line captures the mathematical definition of natural numbers: zero is the base case, and every other natural number is the successor of another natural number. To convert this abstract representation into something the computer can work with:
eval :: Nat -> Int eval Zero = 0 eval ( Succ m ) = 1 + eval m
So 0 becomes Zero, 1 becomes Succ Zero, 2 becomes Succ (Succ Zero), and so on. This direct translation from mathematical definition to code is something you simply can't achieve as elegantly in languages like Python or C.
Lambda Functions:
I want to implement merge sort but to get there we must get through some basics in Haskell. The first topic are lambda functions which are anonymous functions that take arguments and perform operations
-- \arg1 arg2 -> do something with the arguments \ x y -> x + y -- adds two arguments \ x -> x -- identity function
Curried Functions
One of Haskell's most important concepts is currying, which becomes essential when working with functions like map. Since functions in Haskell are mathematical abstractions, passing multiple arguments requires a clever approach.
Instead of passing tuples (which becomes cumbersome), Haskell uses curried functions:
add :: Int -> Int -> Int add x y = x + y
This function appears to take two integers and return their sum, but it's actually more sophisticated. We can rewrite it to reveal what's really happening:
add :: Int -> ( Int -> Int ) add x = \ y -> x + y
The add function takes one argument and returns a new function. When you call add 5, you get a function that adds 5 to whatever you pass it. Then add 5 7 applies that "add 5" function to 7, resulting in 12. We can go a step deeper and using lambdas, we can write
add :: Int -> Int -> Int add = \ x -> ( \ y -> x + y )
This clearly shows that curried functions are functions that return other functions allowing us to have functions that take multiple arguments while still following the rules of functional programming.
The Beauty of Merge Sort in Haskell
This demonstrates several key Haskell concepts: recursion with lists (working toward a base case by processing the head and recursively handling the tail), and pattern matching (different behavior for empty versus non-empty lists).
Let's consider the map function (a curried function) which applies a function to each element in a list recursively.
map :: ( a -> b ) -> [ a ] -> [ b ] map _ [] = [] map f ( x : xs ) = f x : map f xs
This is a typical way to iterate over lists in Haskell. You have a base case of the empty list were you return some value then the recursive case where you use pattern matching to get the first element of the list at the top of the list. These tools will be used in merge sort.
Once I grasped these fundamentals, implementing merge sort revealed Haskell's true elegance:
halve :: [ a ] -> ([ a ], [ a ]) halve xs = ( take ( length xs ` div ` 2 ) xs , drop ( length xs ` div ` 2 ) xs ) merge :: Ord a => [ a ] -> [ a ] -> [ a ] merge [] ys = ys merge xs [] = xs merge ( x : xs ) ( y : ys ) | x < y = x : merge xs ( y : ys ) | otherwise = y : merge ( x : xs ) ys msort :: Ord a => [ a ] -> [ a ] msort [] = [] msort xs = merge ( msort left ) ( msort right ) where ( left , right ) = halve xs
The msort function captures the exact algorithm described in textbooks. There's no index tracking, no confusing logic—just clean, recursive structure that mirrors the mathematical definition perfectly. This is when it hit me that Haskell and the rules of functional programming lead to easy, clean, concise code.
Understanding Reverse Polish Notation
Now let's dive into reverse Polish notation (RPN), also called postfix notation. This system eliminates the need for parentheses in mathematical expressions.
In standard notation:
2 + 3 * 4 equals 14 (due to order of operations)
(2 + 3) * 4 equals 20
In reverse Polish notation:
2 3 4 * + equals 14
2 3 + 4 * equals 20
RPN is fascinating because it maps perfectly onto a stack-based evaluation model. The rule is simple: when you encounter a number, push it onto the stack; when you encounter an operator, pop two numbers, apply the operation, and push the result back. Continue until one item remains.
This made RPN popular in early calculators and trading systems where speed mattered. For computers, it's compelling because evaluation requires only one simple rule, with no need to track precedence or parentheses.
My First RPN Evaluator (And Its Limitations)
Postfix expression evaluation seemed like an easy thing to implement in Haskell and I was hopeful that I would be able to bang this out. My initial implementation worked but had limitations:
evalRpn :: String -> Stack Int -> Stack Int evalRpn [] stack = stack evalRpn ( x : xs ) stack | isDigit x = evalRpn xs (( digitToInt x ) : stack ) | otherwise = evalRpn xs (( applyOp x ( pop2 stack )) : drop 2 stack )
This handled single-digit numbers but failed on inputs like 12 35 + because it couldn't parse multi-digit numbers. I knew I could do better and decided to build a proper parser.
Learning from an Expert
At this point, I knew my RPN implementation wasn't optimal. So I took a chance and emailed Graham Hutton, author of Programming in Haskell. To my amazement, this seasoned professional took time to help a complete novice. Here's his elegant solution:
import Data.Char type Expr = [ Symb ] data Symb = Num Int | Add | Mul deriving Show parse :: String -> Expr parse = map p p :: Char -> Symb p '+' = Add p '*' = Mul p n | isDigit n = Num ( digitToInt n ) eval :: Expr -> [ Int ] -> [ Int ] eval [] s = s eval ( Add : e ) ( n : m : s ) = eval e ( m + n : s ) eval ( Mul : e ) ( n : m : s ) = eval e ( m * n : s ) eval ( Num n : e ) s = eval e ( n : s )
This solution is beautifully compact and works perfectly for expressions like 23+ or 23* (assuming no spaces and single-digit numbers). His use of a new data type was clean and the way I probably should have been thinking about this question the whole time. This was clearly superior to my previous implementation however, it doesn't handle spacing or multi-digit numbers. I wanted to extend this while preserving its clean structure.
Discovering Monads Through a Simple Example
To improve this solution, I needed introduce some parsing. My brother has talked about top-down recursive parsers so I decided to look into creating a parse trees in Haskell. I did not end up making any parse trees but this sent me on the jounery to make a parsers in Haskell. In order make a parser I first needed to understand monads—one of Haskell's most powerful (and confusing) concepts. Monads allow computations to carry additional context, such as the possibility of failure, input/output operations, or parsing state.
Let me illustrate with a simple example: adding two numbers, but failing if their sum exceeds 10:
addLess10 :: Int -> Int -> Maybe Int addLess10 x y | x + y <= 10 = Just ( x + y ) | otherwise = Nothing
The Maybe type can be either Just a (success with value a) or Nothing (failure). Now, suppose I want to sum a list using this rule, failing if any intermediate sum exceeds 10:
addList :: [ Int ] -> Maybe Int addList [] = Nothing addList [ x ] = Just x addList ( x : y : xs ) = addLess10 x y >>= \ res -> addList ( res : xs )
The key is the bind operator >>=, which chains computations together. If any step returns Nothing, the entire computation fails. Here's how the Maybe monad instance makes this work:
instance Monad Maybe where return x = Just x Nothing >>= _ = Nothing Just x >>= f = f x
If we encounter Nothing, the bind operator short-circuits. If we get Just x, it applies the function to x. This automatic error handling is what makes monads powerful.
The same logic becomes cleaner with do notation:
addList :: [ Int ] -> Maybe Int addList [] = Nothing addList [ x ] = Just x addList ( x : y : xs ) = do res <- addLess10 x y addList ( res : xs )
The do notation is just syntactic but it clearly gives us the ability to chain multiple statements together and build larger monadic types. This will serve us well when we start to do parsing.
The Foundation: Parser Type Definition
The true power of monads becomes apparent when building parsers. We can create small, primitive parsers and compose them into larger, more sophisticated ones. For example, we might create a parser that consumes exactly x spaces, or one that reads multi-digit numbers. The key is starting with a solid foundation.
First, we need to define what a parser actually is. The parsing type below and the all the primitives come from Programming in Haskell, here's our base type:
newtype Parser a = P ( String -> [( a , String )]) parse :: Parser a -> String -> [( a , String )] parse ( P p ) inp = p inp
Let's break this down: A Parser a is essentially a wrapper around a function that takes a String and returns a list of tuples. Each tuple contains a result of type a and the remaining unparsed String. If the list is empty, parsing fails. If the list contains results, parsing succeeds.
We write the parse function as an easy way to unwrap our parser and apply it to actual input.
Our First Parser: Reading Single Characters
Now we can build our first concrete parser:
item :: Parser Char item = P ( \ inp -> case inp of [] -> [] ( x : xs ) -> [( x , xs )])
This parser reads exactly one character from the input. If we call parse item "thing", we get [('t', "hing")]—the first character and the rest of the string. We simply pop off the first element of the string.
The Parser Monad: Enabling Composition
Here’s where things get really confusing but where the magic happens. To chain parsers together effectively, we need to define how the Parser type works as a monad:
instance Monad Parser where -- (>>=) :: Parser a -> (a -> Parser b) -> Parser b p >>= f = P ( \ inp -> case parse p inp of [] -> [] [( v , out )] -> parse ( f v ) out )
The bind operator (>>=) is confusing at first, but understanding its type signature helps. It takes:
A parser that produces values of type a A function that takes an a and returns a parser producing b Returns a new parser that produces b
Here's what happens step by step:
Run the first parser p on the input If it fails (returns []), the whole computation fails If it succeeds, extract the value v and remaining input out Apply function f to v to get a new parser Run that new parser on the remaining input out This allows us to sequence parsing operations while automatically handling the threading of remaining input through each step.
Practical Example: Conditional Character Parsing
With our monad instance, we can now write much cleaner parser code:
sat :: ( Char -> Bool ) -> Parser Char sat f = do x <- item if f x then return x else empty
This parser reads a character and only succeeds if that character satisfies the predicate f. Notice how clean this is:
x <- item extracts the character that item parsed
We can work directly with x without worrying about tuples or remaining input
The monad handles all the bookkeeping automatically
Without monads, we'd have to manually manage the parsing state, check for failures, and thread the remaining input through each operation. The monadic interface abstracts away this complexity, letting us focus on the parsing logic itself.
The Power of Composition
This foundation enables us to build increasingly sophisticated parsers by combining simpler ones. Want to parse digits? Spaces? Multi-digit numbers? Each becomes a matter of composing our basic building blocks using the monadic interface.
The beauty is that each parser remains focused on its specific task, while the monad instance handles the complex orchestration of sequencing, error handling, and state management. This is why monadic parsing is so powerful—it gives us both expressiveness and composability without sacrificing clarity.
As we'll see, this approach scales beautifully from simple character-level parsing all the way up to complete expression parsers, all built from the same fundamental building blocks.
Building a Robust Parser with Monadic Parsing
Using monadic parsing techniques, I built a more flexible parser that handles spaces and multi-digit numbers while maintaining the elegance of Hutton's design:
type Expr = [ Symb ] data Symb = Num Int | Add | Mul deriving Show symb :: Parser Symb symb = do n <- token natural return ( Num n ) <|> do symbol "+" return Add <|> do symbol "*" return Mul p :: Parser Expr p = some symb eval :: Expr -> [ Int ] -> [ Int ] eval [] s = s eval ( Add : e ) ( n : m : s ) = eval e ( m + n : s ) eval ( Mul : e ) ( n : m : s ) = eval e ( m * n : s ) eval ( Num n : e ) s = eval e ( n : s )
This implementation keeps Hutton's clear evaluation logic while using monadic parsing to handle complex input. The symb parser reads natural numbers or operators, converting them into symbolic expressions. The eval function interprets the postfix expression using a stack, just as before.
What I love about this solution is its natural behavior: it reads the longest valid expression it can process. If the input has sufficient structure, it evaluates successfully; otherwise, it fails gracefully. The code cleanly separates parsing from evaluation and handles complexity without becoming messy.
Reflections on the Journey
This final version represents several weeks of learning, struggling, and ultimately succeeding. I learned Haskell from scratch, grappled with monads and parsing, and created something genuinely useful. Most importantly, I learned from a world-class teacher who was generous enough to guide a beginner.
My biggest takeaway is this: Haskell is a beautiful and expressive language that rewards the investment of time and effort. The concepts you learn become part of how you think about programming, even in other languages. Having excellent resources like Programming in Haskell and access to knowledgeable mentors makes an enormous difference.
For future projects, I'll remember to lean on authoritative sources and structured learning. Sometimes you don't know what you don't know, and sometimes all it takes to get unstuck is sending one thoughtful email. Thanks for following my journey. I hope it encourages you to take your own side quests, learn deeply, and share what you discover along the way.