Skip to content
Tutorials Center
My learning

Topics

Lesson 51 of 57 ยท Real-world Haskell

Project: JSON Parser from Scratch

Build a JSON parser and pretty printer in Haskell with a small parser-combinator library, then test a round trip. Includes runnable JS models.

JSON is the perfect parsing exercise: the grammar fits on a postcard, but it contains recursion (arrays inside objects inside arrays), choices, repetition and escapes. In this project you build a JSON parser in Haskell without any parsing library, using only a tiny set of parser combinators you write yourself. Then you add a printer and check that printing and parsing are inverse operations.

This lesson builds on Parsing with Parser Combinators, Functors and Applicative Functors. Real Haskell is read-only here; the runnable examples are JavaScript stand-ins that follow the same design, so you can see every step work.

From text to a tree

Text {"a": [1, true]}
Parser Small combinators, glued together.
JSON value A recursive data type.
Printer The tree back to text.

parse and render should be inverses.

1 / 2

Step 1: The data type

JSON has six kinds of value. A sum type says it directly, and the recursion in JArray and JObject mirrors the recursion in the grammar (see Recursive Data Types and Trees):

HASKELL
data JSON
  = JNull
  | JBool Bool
  | JNumber Double
  | JString String
  | JArray [JSON]
  | JObject [(String, JSON)]
  deriving (Show, Eq)

Objects use an association list so key order is preserved. A Data.Map would sort the keys and lose the original order, which matters for a printer that should be faithful to its input.

Step 2: A parser is a function

A parser takes the remaining input and either fails or returns a result together with the input that is still left over:

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

Giving it Functor, Applicative, Monad and Alternative instances is what makes the combinators work. fmap changes the result, <*> runs two parsers in sequence, and <|> tries the second parser only if the first fails:

HASKELL
import Control.Applicative

instance Functor Parser where
  fmap f (Parser p) = Parser $ \input -> case p input of
    Nothing        -> Nothing
    Just (a, rest) -> Just (f a, rest)

instance Applicative Parser where
  pure a = Parser $ \input -> Just (a, input)
  Parser pf <*> Parser pa = Parser $ \input -> case pf input of
    Nothing         -> Nothing
    Just (f, rest)  -> case pa rest of
      Nothing          -> Nothing
      Just (a, rest')  -> Just (f a, rest')

instance Monad Parser where
  Parser p >>= f = Parser $ \input -> case p input of
    Nothing        -> Nothing
    Just (a, rest) -> runParser (f a) rest

instance Alternative Parser where
  empty = Parser (const Nothing)
  Parser p <|> Parser q = Parser $ \input -> case p input of
    Nothing -> q input
    result  -> result

Alternative also gives you many (zero or more) and some (one or more) for free, defined in terms of <|>. Note that this <|> never backtracks into a parser that succeeded; for JSON that is fine because the first character decides which alternative applies.

From one primitive, everything else follows:

HASKELL
import Data.Char (isDigit, isSpace)

satisfy :: (Char -> Bool) -> Parser Char
satisfy ok = Parser $ \input -> case input of
  (c : rest) | ok c -> Just (c, rest)
  _                 -> Nothing

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

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

spaces :: Parser ()
spaces = () <$ many (satisfy isSpace)

token :: Parser a -> Parser a
token p = p <* spaces

sepBy :: Parser a -> Parser b -> Parser [a]
sepBy p sep = sepBy1 p sep <|> pure []

sepBy1 :: Parser a -> Parser b -> Parser [a]
sepBy1 p sep = (:) <$> p <*> many (sep *> p)

string = traverse char is a lovely one-liner: it runs char on every letter of the word in order. The operators *> and <* run both sides but keep only the right or left result, which is perfect for punctuation.

JS A parser-combinator kit in JavaScript

Press Run (or Ctrl + Enter) to see the console output here.

No output.

The shapes match the Haskell exactly: keepRight is *>, keepLeft is <*, alt is <|>, and fmap is <$>. In JavaScript a parser failure is null, where Haskell uses Nothing.

Step 3: The grammar as code

Each JSON construct becomes one small parser, and the top-level parser is an alternative between them. This is the whole grammar:

HASKELL
jsonValue :: Parser JSON
jsonValue = token (jNull <|> jBool <|> jNumber <|> jString <|> jArray <|> jObject)

jNull :: Parser JSON
jNull = JNull <$ string "null"

jBool :: Parser JSON
jBool = (JBool True <$ string "true") <|> (JBool False <$ string "false")

jNumber :: Parser JSON
jNumber = JNumber <$> number

number :: Parser Double
number = do
  sign  <- optional (char '-')
  whole <- some (satisfy isDigit)
  frac  <- optional (char '.' *> some (satisfy isDigit))
  let value = read (whole ++ maybe "" ('.' :) frac) :: Double
  pure (maybe value (const (negate value)) sign)

jString :: Parser JSON
jString = JString <$> stringLiteral

stringLiteral :: Parser String
stringLiteral = char '"' *> many stringChar <* char '"'

stringChar :: Parser Char
stringChar = (char '\\' *> escape) <|> satisfy (\c -> c /= '"' && c /= '\\')

escape :: Parser Char
escape =  ('"'  <$ char '"')
      <|> ('\\' <$ char '\\')
      <|> ('\n' <$ char 'n')
      <|> ('\t' <$ char 't')

jArray :: Parser JSON
jArray = JArray <$> (char '[' *> spaces *> sepBy jsonValue (token (char ',')) <* char ']')

jObject :: Parser JSON
jObject = JObject <$> (char '{' *> spaces *> sepBy pair (token (char ',')) <* char '}')
  where
    pair = (,) <$> token stringLiteral <* token (char ':') <*> jsonValue

<$ replaces a successful result with a constant: JNull <$ string "null" means "match the word, then produce JNull". jArray and jObject call jsonValue, which calls them back: that mutual recursion is how nested data is parsed, and laziness makes it work without any special syntax.

This version is deliberately small. It does not handle exponents (1e5), \uXXXX escapes, or a leading +. Adding them is a good exercise. The entry point demands that all input is consumed:

HASKELL
parseJSON :: String -> Maybe JSON
parseJSON input = case runParser (spaces *> jsonValue) input of
  Just (value, "") -> Just value
  _                -> Nothing

A returned Nothing says "invalid" but not where. A production parser tracks the position and returns an Either ParseError (the next steps below mention this, and libraries such as megaparsec do it for you).

Step 4: Printing

Rendering is a plain recursive function over the data type. Compact output first:

HASKELL
import Data.List (intercalate)

render :: JSON -> String
render JNull         = "null"
render (JBool True)  = "true"
render (JBool False) = "false"
render (JNumber n)
  | n == fromIntegral r = show r
  | otherwise           = show n
  where r = round n :: Integer
render (JString s)   = renderString s
render (JArray xs)   = "[" ++ intercalate "," (map render xs) ++ "]"
render (JObject kvs) =
  "{" ++ intercalate "," [renderString k ++ ":" ++ render v | (k, v) <- kvs] ++ "}"

renderString :: String -> String
renderString s = "\"" ++ concatMap escapeChar s ++ "\""
  where
    escapeChar '"'  = "\\\""
    escapeChar '\\' = "\\\\"
    escapeChar '\n' = "\\n"
    escapeChar '\t' = "\\t"
    escapeChar c    = [c]

An indented printer takes the current depth as an extra argument, which is the standard trick for formatting trees. Empty containers stay on one line:

HASKELL
pretty :: Int -> JSON -> String
pretty _ (JArray [])  = "[]"
pretty _ (JObject []) = "{}"
pretty n (JArray xs) =
  "[\n" ++ intercalate ",\n" [pad (n + 2) ++ pretty (n + 2) x | x <- xs]
        ++ "\n" ++ pad n ++ "]"
pretty n (JObject kvs) =
  "{\n" ++ intercalate ",\n"
             [pad (n + 2) ++ renderString k ++ ": " ++ pretty (n + 2) v | (k, v) <- kvs]
        ++ "\n" ++ pad n ++ "}"
pretty _ other = render other

pad :: Int -> String
pad n = replicate n ' '
JS The whole parser, printer and a round trip

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Step 5: The round-trip property

The best test for a parser and printer pair is a property: for every value v, parseJSON (render v) == Just v. QuickCheck generates random trees for you (see Testing: HUnit, Hspec and QuickCheck). You only have to say how to build a value, limiting depth so the generator terminates:

HASKELL
import Test.QuickCheck

instance Arbitrary JSON where
  arbitrary = sized gen
    where
      gen 0 = oneof [pure JNull, JBool <$> arbitrary, JNumber . fromIntegral <$> (arbitrary :: Gen Int), JString <$> arbitrary]
      gen n = oneof
        [ gen 0
        , JArray <$> resize (n `div` 2) (listOf (gen (n `div` 2)))
        , JObject <$> resize (n `div` 2) (listOf ((,) <$> arbitrary <*> gen (n `div` 2)))
        ]

prop_roundTrip :: JSON -> Bool
prop_roundTrip v = parseJSON (render v) == Just v

Running it would quickly reveal that random strings contain characters such as \r that renderString does not escape, or that show for very large or tiny doubles produces 1.0e-2, which the number parser cannot read. A failing property with a shrunk counterexample is exactly how real parsers get fixed.

Ideas for extending it

  • Report errors with a line and column using Either ParseError.
  • Support exponents and \uXXXX escapes.
  • Write query helpers like getKey :: String -> JSON -> Maybe JSON and a path lookup.
  • Compare your parser with the aeson library from JSON and Web Services.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What is the type of a parser in this project?

    A parser takes the input and returns either failure or a result plus the unconsumed input.
  2. 2. What does JNull <$ string "null" do?

    <$ runs the parser on its right and replaces the successful result with the constant on its left.
  3. 3. Why does JObject use [(String, JSON)] rather than a Map?

    An association list keeps keys in the order they appeared, which a printer can reproduce.
  4. 4. What does the round-trip property check?

    Printing then parsing should return the original value; random tests find edge cases in either direction.
  5. 5. What does some p mean compared to many p?

    many accepts zero or more repetitions; some requires at least one.

Summary

  • A JSON value is a recursive sum type; the parser mirrors its structure.
  • A parser is a function String -> Maybe (a, String) wrapped in a newtype, with Functor, Applicative, Monad and Alternative instances.
  • <$, <*, *>, <|>, many, some and sepBy combine small parsers into the whole grammar.
  • Printing is a recursive function; an extra indent argument gives a pretty printer.
  • The property parseJSON (render v) == Just v is a powerful test that finds edge cases.

Next: Project: Text Adventure Engine.