Taking The Parser Combinator Pill

• functional-programming
• parser-combinators
• monads
• haskell

The World Is Your Parser

I recently discovered the elegance and expressive power of parsing using parser combinators recently and I immediately fell in love with it, wanting to use it to solve new problems using it.

In fact, I used parser combinators to parse a mini programming language, Core, following in close step to "Implementing functional languages: a tutorial" by Simon Peyton Jones, one of the founders of Haskell. I also used parser combinators to implement a parser for the UCI protocol in NodeJS while writing an adapter for another project. And then I implemented the same parser in Gleam, which I'll link to once I make the repo public.

It's just so satisfying to break down a seemingly complicated language specification down to atoms in a disciplined manner and reconstruct the full language through the power of parser combinators.

But I'm getting ahead of myself.

We'll talk a bit about the theory behind parser combinators and build up to writing a fully-functional parser combinator in Haskell to parse JSON.

Don't worry if you don't know much Haskell. I'll try to keep things simple and explain things as we go. However, I expect readers to be a bit more mature than my previous post on monads. There will be less hand-holding throughout this post for sake of brevity, and I expect readers to be able to piece things together themselves.

Parser? I hardly know her!

...This joke doesn't really work here, does it?

So what even are parser combinators? Well, in general, a combinator in the context of programming is just something that... combines things. So a parser combinator is just something that combines parsers.

The idea is that if we can parse, say, the literal string "true", then we should be able to parse multiple "true"s. And if we can parse a comma and whitespaces, then we should also be able to parse "true" separated by commas and whitespaces. The way we do this is by combining parsers. Parser combinators!

This is really vague if you're new to parser combinators, so we'll dive into code examples immediately. Just keep the idea of being able to "combine" parsers in the back of your head.

Aside: Haskell Workflow

Let's get you set up with a comfortable Haskell workflow so you're able to follow along with these examples.

First, you need to install Haskell.

Once that's done, create a new project and create a file called Main.hs with the following contents:

module Main where

main :: IO ()
main = do
  putStrLn "Hello, World!"

In a terminal, navigate to the directory containing Main.hs and run ghci, which will spawn a new interactive environment to run Haskell code.

Run :l Main.hs to load the file, and then run main. You should see Hello, World! printed to the terminal.

Now, let's add another function:

module Main where
...
double :: Int -> Int
double x = x * 2

In the existing GHCi session, you can just type :r to reload the file. Now you can actually call double 5 to execute the code you just wrote.

This is my preferred Haskell development workflow, where you make some changes to a file, reload, and then immediately start executing code interactively.

The Parser

The basic building block of parser combinators – the thing that's being combined – is, of course, the parser. Let's define a parser.

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

Equivalently, in TypeScript,

type Parser<A> = (x: string) => [A, string] | null

A Parser a is something that accepts an input (in our case, we are restricting ourselves to string inputs) and produces an a along with the rest of the input if successful, or it produces nothing if it fails.

Character Parser

So we might define a function to create a parser to parse a single character like so:

char :: Char -> Parser Char
char c = f
  where
    f (x:xs)
      | x == c    = Just (c, xs)
      | otherwise = Nothing
    f [] = Nothing

In English, char is a function that accepts a character c and returns a function that checks if the first character is c. If it is, then return the successfully parsed c and the rest of the string. Otherwise, if c didn't match or the input was empty, then return an error result.

If you reload GHCi with :r and run char 'a' "abcd", you should get Just ('a', "bcd"). We've successfully created a parser to parse a character!

Now, we'll set our sights on parsing a literal string.

String Parser

An obvious way of parsing strings might be to write something like this:

module Main where

import Data.List
...
str :: String -> Parser String
str s = f
  where
    f input
      | s `isPrefixOf` input = Just (s, drop (length s) input)
      | otherwise            = Nothing

You can verify that it works by running str "foo" "foo bar baz" and getting Just ("foo", " bar baz").

However, this is not a very combinatorial approach. If we're able to parse individual characters, surely we should be able to combine a parser that parses 'f', a parser that parses 'o', and a parser that parses 'o' to create a parser that parses "foo", right?

Indeed, we can! But before we do that, we need to upgrade our parser slightly and prove to Haskell that it's a monad. In doing this, we unlock a ton of features for our Parser that we'll use anyway, so we're not preemptively overengineering.

Training Arc

If you look at the reference for Monads on Haskell, you'll find:

class Applicative m => Monad (m :: Type -> Type) where
  ...

This just tells us that in order to be a Monad, our parser has to be an Applicative first. Okay, clicking into Applicative, we see this:

class Functor f => Applicative (f :: Type -> Type) where
  ...

Alright, so our parser has to be a Functor first. Looking at the reference for Functor, we have to prove that our parser supports the fmap, or functor map operation.

To do this, we need to define our parser using the newtype syntax. I won't get into why, but using newtype to prove typeclasses is very common in Haskell.

newtype Parser a = Parser
  { runParser :: String -> Maybe (a, String)
  }

This is essentially the same definition as before, but we just have to put Parser in front of the parsing function. So our char function just has to be changed to this:

char :: Char -> Parser Char
char c = Parser f
  where
    f (x:xs)
      | x == c    = Just (c, xs)
      | otherwise = Nothing
    f [] = Nothing

Additionally, if you want to run the parser now, you have to call runParser (char 'a') "abcd".

Functor

Alright, now let's prove Parser is a Functor.

instance Functor Parser where
  fmap f (Parser p) = Parser $ \input -> do
    (a, input') <- p input
    return (f a, input')

fmap is a function that maps the "inner" value of Parser. What that amounts to is: we run a Parser a on the input to get an (a, input'), where input' is the rest of the input after parsing the a, and then we simply transform a into f a before returning it.

Let's see it in action:

ghci> runParser (char 'a') "abcd"
Just ('a',"bcd")

This is expected. But what if we wanted to get the character code of the character that we parsed instead? Try this:

ghci> import Data.Char (ord)
ghci> runParser (fmap ord (char 'a')) "abcd"
Just (97,"bcd")

We transformed the "inner" value 'a' into its character code using ord by using fmap. Another way to write this would be:

ghci> runParser (ord <$> char 'a') "abcd"
Just (97,"bcd")

Here, the <$> acts like the regular $ function in Haskell, except the function gets to "inject" itself into a functor. It's really just an infix version of fmap.

If we really want our Parser to behave properly as a Functor, there are functor laws we should also prove (this proof takes place outside of code). I'll leave proving the functor laws as an exercise to the reader.

Applicative

We're finished with one-third of our side quest. Now we just have to prove Parser is an Applicative. According to the reference, we need to implement two functions: pure and (<*> or liftA2).

Let's start by implementing pure.

instance Applicative Parser where
  pure a = Parser $ \input -> Just (a, input)

There's basically no other way we could implement pure. After all, pure is supposed to be a function that accepts an a and returns a Parser a. The only sane choice is to create a Parser that always returns a, regardless of the input.

Moving on to liftA2,

instance Applicative Parser where
  ...
  liftA2 g (Parser pa) (Parser pb) = Parser $ \input -> do
    (a, input') <- pa input
    (b, input'') <- pb input'
    return (g a b, input'')

liftA2 in general allows us to apply functions to values within functors. For example, if we had a Maybe a and a Maybe b and a function a -> b -> c, I should be able to unwrap the a and b out of the Maybes and then run a -> b -> c to get a Maybe c right? Or if one of the Maybes was a Nothing, then we should end up returning Nothing. The same logic applies to liftA2 on Parsers.

To verify it works, let's check it in GHCi:

ghci> runParser (liftA2 (\x y -> [x,y]) (char 'a') (char 'b')) "abcd"
Just ("ab","cd")

What's happening is that liftA2 (\x y -> [x, y]) is "lifting" the lambda expression into the world of Parsers so that we can apply it to values inside char 'a' and char 'b'.

Commonly, you'll also see this being written as

runParser ((\x y -> [x, y]) <$> (char 'a') <*> (char 'b')) "abcd"

This is because it allows you to chain more arguments easily. If you also wanted to parse a 'c', then you could just just add to the expression:

ghci> runParser ((\x y z -> [x, y, z]) <$> (char 'a') <*> (char 'b') <*> (char 'c'))  "abcd"
Just ("abc","d")

Monad

Final stretch. Monads only require the >>= operation, or bind to be implemented.

instance Monad Parser where
  (Parser pa) >>= f = Parser $ \input -> do
    (a, input') <- pa input
    let (Parser pb) = f a
    pb input'

We can more or less play "type tetris" to implement this. We have that pa :: String -> Maybe (a, String), f :: a -> Parser b and we need to return a Parser b. The obvious choice is to run the pa on the input to get an a, and then get a Parser pb from f a, and then return pb on input', the input after parsing the a.

Now we can define a parser to parse the string "true"!

true :: Parser Bool
true = do
  _ <- char 't'
  _ <- char 'r'
  _ <- char 'u'
  _ <- char 'e'
  return True

Or you can even write it like this:

true :: Parser Bool
true =
  char 't' >>
  char 'r' >>
  char 'u' >>
  char 'e' >>
  return True

Let's check that it works:

ghci> runParser true "true false"
Just (True," false")

Pretty neat, huh? And don't worry if this is still too cumbersome. We're on our way to creating a function that accepts any string and creates a parser that parses that string. By then, we should be able to define true = str "true" >> return True.

Similar to the functor laws, we should check that our monad satisfies the monad laws, which I'll leave as an exercise to the reader.

Alternative

While we're at it, let's implement Alternative on our Parser, which will allow us to do things like pa <|> pb, which is a parser that tries to parse pa first, and if it fails, then parse pb.

instance Alternative Parser where
  empty = Parser (const Nothing)
  (Parser p1) <|> (Parser p2) = Parser $ \input ->
    p1 input <|> p2 input

This one's easy. empty needs to give a Parser a. Well, how can we even create a Parser a? We can't. So we have to create a Parser that always fails.

Since Maybe is itself an Alternative, we can just run each parser on the input and then use the implementation for <|> on Maybe to implement <|>.

Let's test it out by writing a parser for False and then trying to parse "true" or "false".

false :: Parser Bool
false =
  char 'f' >>
  char 'a' >>
  char 'l' >>
  char 's' >>
  char 'e' >>
  return False

Let's check that it works in GHCi:

ghci> runParser (true <|> false) "false"
Just (False,"")
ghci> runParser (true <|> false) "true"
Just (True,"")

String Parser Mk. 2

Let's finally re-define str now that we have the power of the monad. The idea is that, since String is literally type-aliased as a [Char], we can map each Char into a Parser Char using our char function, and then do a fold. Roughly,

-- str "true"
-- Turns into a [Parser Char]
-- [char 't', char 'r', 'char u', 'char e']
-- Turns into a Parser [Char]
-- char 't' `(liftA2 (:))` (char 'r' `(liftA2 (:))` ...)

We can translate that into:

str :: String -> Parser String
str s = foldr (liftA2 (:)) (pure "") $ map char s

But it turns out this sort of operation is common enough that there are shortcuts to writing them.

ghci> :t traverse
traverse
  :: (Traversable t, Applicative f) => (a -> f b) -> t a -> f (t b)
ghci> :t mapM
mapM :: (Traversable t, Monad m) => (a -> m b) -> t a -> m (t b)

The general pattern is that we're able to turn an [Char] into an [Parser Char], but what we really wanted was an Parser [Char]! traverse or mapM allows us to "turn the applicative/monad inside out of a list" as long as we know how to turn each element of the list into a monad/applicative. traverse is more general because it only requires that f be an Applicative, which Monad must satisfy already. In fact mapM is literally defined to be traverse. So let's use it.

str :: String -> Parser String
str s = traverse char s

With an eta reduction, we can get:

str :: String -> Parser String
str = traverse char

Yup, this is our entire function. If you're newer to Haskell and functional programming, you might accuse me of making this unreadable compared to what we had before, either the version with foldr or the version with isPrefixOf, but as you get to understand Haskell, you'll realize this is a much more natural and elegant solution compared to the previous iterations. Again, the key to traverse is recognizing that we're just "turning the applicative inside out of a list" (more generally, any Traversable).

Let's rewrite true and false with our upgraded str function:

true :: Parser Bool
true = str "true" >> return True

false :: Parser Bool
false = str "false" >> return False

And we may as well write a parser for a Bool in general:

bool :: Parser Bool
bool = true <|> false

Combinators

I mentioned before that we should be able to take existing parsers and "combine" them to parse bigger things, right? Well, we actually already have one for free: many. We get to use it for free because we proved Parser was an Alternative!

Try it out, it works exactly like you think:

ghci> runParser (many (str "foo")) "foofoofoobar"
Just (["foo","foo","foo"],"bar")
ghci> runParser (many (str "foo")) ""
Just ([],"")

I want to remind the reader that the end goal is to parse JSON. So let's define combinators to help us do that.

Warmup

Let's start by defining many1, which is exactly like many, except it requires parsing at least one item.

many1 :: Parser a -> Parser [a]
many1 pa = do
  a <- pa
  as <- many pa
  return (a:as)

Put more succinctly,

many1 :: Parser a -> Parser [a]
many1 pa = (:) <$> pa <*> many pa

(If you feel uncomfortable with notation, don't use it! Stick with what works for you.)

Separator

sepBy will take two parsers and give us a parser that alternates between using each parser. We should end up with something like this:

ghci> runParser (bool `sepBy` (str ", ")) "true, false, true, true foo bar"
Just ([True, False, True, True], " foo bar")

Let's try this:

sepBy :: Parser a -> Parser b -> Parser [a]
sepBy pa sep = do
  a <- pa
  as <- many (sep >> pa)
  return (a:as)

We first have to parse using pa, and then we parse a bunch of seps, ignore the result (that's what >> is doing), and parse using pa.

Giving it a go in GHCi:

ghci> runParser (bool `sepBy` (str ", ")) "true, false, true"
Just ([True,False,True],"")
ghci> runParser (bool `sepBy` (str ", ")) ""
Nothing

Ah, but we should be parsing an empty string as [], not failing. Let's make it so that if we failed to parse, then we just return an [], using our <|> operator.

sepBy :: Parser a -> Parser b -> Parser [a]
sepBy pa sep =
  ( do
      a <- pa
      as <- many (sep >> pa)
      return (a:as)
  ) <|> return []

Now it's fixed!

ghci> runParser (bool `sepBy` (str ", ")) ""
Just ([],"")

Written a bit more succinctly:

sepBy :: Parser a -> Parser b -> Parser [a]
sepBy pa sep = ((:) <$> pa <*> many (sep >> pa)) <|> return []

(Again, don't use this if you're not comfortable with this.)

Between

We want a combinator like this:

ghci> runParser (between (char '[') (char ']') bools) "[true, false, true]"
Just ([True,False,True],"")

This one's pretty simple and I won't even bother explaining it.

between :: Parser a -> Parser b -> Parser c -> Parser c
between pl pr pc = do
  _ <- pl
  c <- pc
  _ <- pr
  return c

Put more succinctly,

between :: Parser a -> Parser b -> Parser c -> Parser c
between pl pr pc = pl *> pc <* pr

Parsing JSON

We've built all the ingredients we need to parse JSON. To make life a bit easier, let's first build a couple of common parsers we'll be using. These are also parsers that you'll likely take along with you to parse other things.

satisfy :: (Char -> Bool) -> Parser Char
satisfy pr = Parser f
  where
    f (x:xs)
      | pr x      = Just (x, xs)
      | otherwise = Nothing
    f [] = Nothing

oneOf :: String -> Parser Char
oneOf s = satisfy (`elem` s)

noneOf :: String -> Parser Char
noneOf s = satisfy (not . (`elem` s))

digit :: Parser Char
digit = oneOf "0123456789"

whitespaces :: Parser ()
whitespaces = many (oneOf "\r\n\t ") >> return ()

commaSep :: Parser a -> Parser [a]
commaSep pa = pa `sepBy` (char ',' >> whitespaces)

doubleQuoted :: Parser a -> Parser a
doubleQuoted = between (char '"') (char '"')

brackets :: Parser a -> Parser a
brackets = between (char '[') (char ']')

curlies :: Parser a -> Parser a
curlies = between (char '{') (char '}')

Let's define an AST for JSON to store our data into:

data JSON
  = JSONNull
  | JSONBool   Bool
  | JSONNumber Float
  | JSONString String
  | JSONArray  [JSON]
  | JSONObject [(String, JSON)]
  deriving (Eq, Show)

Great, let's knock out the easy ones right off the bat:

jsonNull :: Parser JSON
jsonNull = JSONNull <$ str "null"

jsonBool :: Parser JSON
jsonBool = JSONBool <$> ((True <$ str "true") <|> (False <$ str "false"))

Again, don't be scared of the notation. We already discussed how to parse Bools, so if you're uncomfortable with this, fall back to using that.

Parsing numbers is a little bit tougher because we have to account for the fact that numbers can be written with or without the .. We can easily split it into two cases though:

jsonNumber :: Parser JSON
jsonNumber = JSONNumber <$> (float <|> int)
  where
    float = read <$>
      ((++) <$> many1 digit <*> ((:) <$> char '.' <*> many1 digit))
    int = read <$> many1 digit

It's a little bit ugly because we end up using read to turn the String into a Float, but it works:

ghci> runParser jsonNumber "1.23"
Just (JSONNumber 1.23,"")
ghci> runParser jsonNumber "111"
Just (JSONNumber 111.0,"")

Now, JSON strings are a bit harder to parse because they might contain escape characters like \" or \n. We're going to keep things simple and ignore escape characters.

jsonCapableString :: Parser String
jsonCapableString = doubleQuoted (many (noneOf "\""))

jsonString :: Parser JSON
jsonString = JSONString <$> jsonCapableString

We have a separate jsonCapableString because we need a Parser String to parse keys in JSON object the same way we parse regular strings.

For the recursive definitions, let's first write a parser for any JSON value:

json :: Parser JSON
json =
  jsonNull <|>
  jsonBool <|>
  jsonNumber <|>
  jsonString

A JSONArray is just a bunch of JSONs, separated by commas.

jsonArray :: Parser JSON
jsonArray = JSONArray <$> brackets (commaSep json)

Let's upgrade our main parser:

json :: Parser JSON
json =
  jsonNull <|>
  jsonBool <|>
  jsonNumber <|>
  jsonString <|>
  jsonArray

Testing it out in GHCi, it seems to work:

ghci> runParser json "[true, false, null, 1, 1.1, \"foo\", []]"
Just (JSONArray [JSONBool True,JSONBool False,JSONNull,JSONNumber 1.0,JSONNumber 1.1,JSONString "foo",JSONArray []],"")

Finally, let's implement our parser for the JSONObject.

jsonObject :: Parser JSON
jsonObject = JSONObject <$> curlies (commaSep entry)
  where
    entry = do
      key <- jsonCapableString
      whitespaces >> char ':' >> whitespaces >> return ()
      value <- json
      return (key, value)

Let's upgrade our main parser for the last time:

json :: Parser JSON
json =
  jsonNull <|>
  jsonBool <|>
  jsonNumber <|>
  jsonString <|>
  jsonArray <|>
  jsonObject

And to make sure it all parses, let's try something in GHCi:

ghci> runParser jsonObject "{\"foo\": [true, false, null, 1, 1.1, \"foo\", []], \"bar\": \"baz\"}"
Just (JSONObject [("foo",JSONArray [JSONBool True,JSONBool False,JSONNull,JSONNumber 1.0,JSONNumber 1.1,JSONString "foo",JSONArray []]),("bar",JSONString "baz")],"")

Glorious. A functional JSON parser all within 126 lines of code.

As an exercise, you should try to parse JSON strings with escape characters to complete the spec.

Improvements/Variations

Error Reporting

If you wanted to turn this into a proper parser combinator library, there's one main thing we're lacking: error reporting. Currently, if we fail to parse, we just return a Nothing, but this isn't very helpful.

You might want to make the Parser return an Either so that if something failed to parse, you can report the error.

newtype Parser a = Parser
  { runParser :: String -> Either ParseError (a, String)
  }

type ParseError = String

Additionally, for even better reporting, you should consider keeping track of the position in the original string: things like the line number and character in the column would be a lot of help.

newtype Parser a = Parser
  { runParser :: Input -> Either ParseError (a, Input)
  }

type ParseError = String
data Input = Input
  { inputLine :: Int,
    inputColumn :: Int,
    inputStr :: String
  }

Unordered Input

We've been parsing Strings as a stream of characters using our parser combinators, but it's easy to imagine parsing other things. Other streams are trivially easy. But what about parsing something like command line flags, where order doesn't matter?

In this case, we would have to change our strategy slightly.

newtype ArgParser a = ArgParser
  { runArgParser :: Args -> Maybe (a, Args)
  }

type Args = [String]

The function signature looks the same, but the strategy to "consume" something is slightly different. While String represented a continuous stream of data to consume top to bottom, Args represented an unordered bag of items we try to pick from. Here's what an ArgParser for a "--verbose" flag might look like:

findPop :: (a -> Bool) -> [a] -> Maybe (a, [a])
findPop _ [] = Nothing
findPop p (x:xs)
  | p x       = Just (x, xs)
  | otherwise = case findPop p xs of
                  Just (y, ys) -> Just (y, x:ys)
                  Nothing      -> Nothing

verbose :: ArgParser Bool
verbose = ArgParser f
  where
    f args = case findPop ("--verbose" ==) args of
               Just (_, args') -> Just (True, args')
               Nothing         -> Just (False, args)

Of course, if we do this type of parsing, we'd have to rework a lot of things, and we might not be able to make our parser monadic, depending on how you approach it.

If you're interested in this style of parsing, you might want to see optparse-applicative.

Wrapping Up

Learning to use parser combinators has sparked a renaissance in parsing as well as in how I approach writing code in general. I had been familiar with functional programming for a long while, but I never realized how amazingly expressive and powerful code could be if the core tenet of composability was upheld. It's not hard to imagine creating a combinatory library for other domains in a similar way so long as your functions remain composable.

I can't imagine a world without parser combinators now. I've eaten the forbidden fruit. And if you understood this post, you have too.

Anyway, here's the final code for the entire JSON parser. It is missing some things like being able to parse negative numbers, numbers in the form 10e6, escape characters in string, etc., but it's got the core of a legitimate JSON parser. It's only 126 lines long and I don't want to even bother creating an entire repository for it.

module ParserCombinators where

import           Control.Applicative

data JSON
  = JSONNull
  | JSONBool   Bool
  | JSONNumber Float
  | JSONString String
  | JSONArray  [JSON]
  | JSONObject [(String, JSON)]
  deriving (Eq, Show)

newtype Parser a = Parser
  { runParser :: String -> Maybe (a, String)
  }

instance Functor Parser where
  fmap f (Parser p) = Parser $ \input -> do
    (a, input') <- p input
    return (f a, input')

instance Applicative Parser where
  pure a = Parser $ \input -> Just (a, input)
  liftA2 g (Parser pa) (Parser pb) = Parser $ \input -> do
    (a, input') <- pa input
    (b, input'') <- pb input'
    return (g a b, input'')

instance Alternative Parser where
  empty = Parser $ const Nothing
  (Parser p1) <|> (Parser p2) = Parser $ \input ->
    p1 input <|> p2 input

instance Monad Parser where
  (Parser pa) >>= f = Parser $ \input -> do
    (a, input') <- pa input
    let (Parser pb) = f a
    pb input'

char :: Char -> Parser Char
char c = satisfy (c ==)

str :: String -> Parser String
str = traverse char

satisfy :: (Char -> Bool) -> Parser Char
satisfy pr = Parser f
  where
    f (x:xs)
      | pr x      = Just (x, xs)
      | otherwise = Nothing
    f [] = Nothing

oneOf :: String -> Parser Char
oneOf s = satisfy (`elem` s)

noneOf :: String -> Parser Char
noneOf s = satisfy (not . (`elem` s))

digit :: Parser Char
digit = oneOf "0123456789"

whitespaces :: Parser ()
whitespaces = many (oneOf "\r\n\t ") >> return ()

commaSep :: Parser a -> Parser [a]
commaSep pa = pa `sepBy` (char ',' >> whitespaces)

doubleQuoted :: Parser a -> Parser a
doubleQuoted = between (char '"') (char '"')

brackets :: Parser a -> Parser a
brackets = between (char '[') (char ']')

curlies :: Parser a -> Parser a
curlies = between (char '{') (char '}')

sepBy :: Parser a -> Parser b -> Parser [a]
sepBy pa sep = ((:) <$> pa <*> many (sep >> pa)) <|> return []

many1 :: Parser a -> Parser [a]
many1 pa = (:) <$> pa <*> many pa

between :: Parser a -> Parser b -> Parser c -> Parser c
between pl pr pc = pl *> pc <* pr

jsonNull :: Parser JSON
jsonNull = JSONNull <$ str "null"

jsonBool :: Parser JSON
jsonBool = JSONBool <$> ((True <$ str "true") <|> (False <$ str "false"))

jsonNumber :: Parser JSON
jsonNumber = JSONNumber <$> (float <|> int)
  where
    float = read <$>
      ((++) <$> many1 digit <*> ((:) <$> char '.' <*> many1 digit))
    int = read <$> many1 digit

jsonCapableString :: Parser String
jsonCapableString = doubleQuoted (many (noneOf "\""))

jsonString :: Parser JSON
jsonString = JSONString <$> jsonCapableString

jsonArray :: Parser JSON
jsonArray = JSONArray <$> brackets (commaSep json)

jsonObject :: Parser JSON
jsonObject = JSONObject <$> curlies (commaSep entry)
  where
    entry = do
      key <- jsonCapableString
      whitespaces >> char ':' >> whitespaces >> return ()
      value <- json
      return (key, value)

json :: Parser JSON
json =
  jsonNull <|>
  jsonBool <|>
  jsonNumber <|>
  jsonString <|>
  jsonArray <|>
  jsonObject