How to write your own JSON parser using functional TypeScript & fp-ts -part I
JSON is an omnipresent format that can be read by every mainstream language in the wild. It is well-specified and simple-yet-complex enough to make writing a parser a challenging and fun test of our programming skill.
In the first post of this two part series, we lay down the basic components for building a general string parser. In the second post, we will focus more on the actual JSON format specification and parsing every part of it. In the end, we will have a fully functional JSON parser (think of the native JSON.parse function).
We will use TypeScript and the fp-ts library, and basic knowledge of functional concepts (function composition, immutability) and data types (Option, Either) is expected. The beauty of functional programming is that it allows us to build complex things from simple ones, and that is exactly how we are going to build our JSON parser — by combining simple things.
Shaping the parser
First we’ll give our parser some shape by defining some types. Every parser needs an input and ours is no exception.
Defining parser type
With input present, we can define a type representing the parser — Parser. It’s a function that, when given some input, returns a parsed value of type A and the rest of the input. Parsing can fail, so we’ll wrap return value in Either type and define ParserError to represent all the stuff that can go wrong during parsing.
The advance function will read one character from the input and return it with the rest of the input. The return value is wrapped inside Option in order to represent the state when there are no more chars to read. Note that input is immutable — we are creating a new instance every time we advance the position.
Building the first parser
Now we have everything in place to build our first parser — one capable of no less than parsing a specific character! We will read a single character from input using an advanced function and check to see if it matches the expected character.
Time to see if our parser behaves correctly.
Checking functionality
First, we’ll create a helper for displaying parser results as a human-readable string. We handle both possible outcomes, failure and success (represented by Either type’s left & right value). Notice that our parser is returning a string value. If we want it to return a number, we can transform parsers the same way we transform values inside an array using the map function.
Changing value types
We have defined a map function that can be easily used inside a pipe function. Implementation was simple — we just applied function f to a successfully parsed value. Using map, we can transform our Parser
Combining multiple parsers into sequence
Parsing a simple char was fun, but how about combining multiple parsers into one that could parse the whole word? The product function does nothing more than apply the first parser, applying the second one and combining their results into one tuple.
We can generalize this concept further to create a function sequence that can combine any number of Parser instances. Notice that we are turning the type inside out — we provide the function with ReadonlyArray<Parser>, and get Parser<ReadonlyArray> as a result.
In order to implement the sequence, we also need a parser that always succeeds as it will be used as a starting value for reducing the array of parsers. A sequence of parsers succeeds when all parsers succeed. Obviously, this will never fail for an empty sequence, so by combining empty sequences we get the parser that always succeeds.
Combining parsers with multiple options
We often come across a situation where we want our parser to choose from multiple options. In contrast to sequence, the oneOf function yields a failing parser when it passes an empty list of possible parsers. The reason is simple: it must be true that there is a parser that succeeds, but this condition is not met for an empty list.
One last function combining parsers — many. It will run a given parser repeatedly until it fails, and will succeed when parsing succeeds at least once.
Now we have the basic building blocks to create more complex parsers. As promised, next time we will dig deeper into the JSON specifications, try to represent it in TypeScript, and parse it using our own parser.
Stay tuned…and functional!
