There are a number of posts about decoding recursive JSON in Elm, but I still found it was a slightly tricky task, particularly because the way the Elm compiler deals with recursion requires a workaround in the decoder code to avoid rather confusing runtime errors. In this post, I’d like to tell the story of implementing recursive decoders.

The path to a recursive decoder

The basic structure of the JSON we need to decode is like this (this happens to be the PostgreSQL EXPLAIN command output):

[
  {
    "Plan": {
      "Node Type": "CTE Scan",
      ... 
      "Plans": [
        {
          "Node Type": "Hash",
          ...
          "Plans": [
            {
              "Node Type": "Seq Scan"
              ...
            }
          ]
        }
      ]
    },
    "Execution Time": 1.123
  }
]

The top level is a node, and each node can have a list of child nodes under the Plans key (repeated recursively).

Our first naive attempt at writing a decoder for this structure might look like this:

module Main exposing (main)

import Html exposing (Html, text)
import Json.Decode as Decode
import Json.Decode.Pipeline exposing (..)

json = """
  {
    "Plan": {
      "Node Type": "CTE Scan",
      "Plans": [
        {
          "Node Type": "Hash",
          "Plans": [
            {
              "Node Type": "Seq Scan"
            }
          ]
        }
      ]
    }
  }
"""

type alias PlanJson =
    { executionTime : Float
    , plan : PlanNode
    }

type alias PlanNode =
    { nodeType: String
    , plans: List PlanNode
    }

decodeJson = 
    decode PlanJson 
        |> optional "Execution Time" Decode.float 0
        |> required "Plan" decodePlanNode

decodePlanNode = 
    decode PlanNode 
        |> required "Node Type" Decode.string
        |> optional "Plans" (Decode.list decodePlanNode) []


main : Html msg
main =
    let 
        output =
            case Decode.decodeString decodeJson json of
                Ok { executionTime, plan } ->
                    plan.plans.nodeType

                Err err ->
                    "Couldn't decode JSON"
    in
        text output

This makes the compiler complain about the recursive type alias PlanNode which refers to itself in its definition.

The compiler suggests replacing the type alias with a type:

type PlanNode
    = PlanNode { nodeType : String, plans : List PlanNode }

This doesn’t alleviate the issue, however, because attempting to compile with the updated type definition makes the compiler lament the recursive definition of decodePlanNode instead (this function also refers to itself, without a clear end to the recursion). A different approach is needed.

How about introducing a separate Plans type which PlanNode will refer to?:

type alias PlanNode 
    { nodeType: String
    , plans: Plans
    }

type Plans
    = Plans (List PlanNode)

Correspondingly, we’ll have two decoders in an attempt to sidestep the recursive definition of decodePlanNode:

decodePlanNode = 
    decode PlanNode 
        |> required "Node Type" Decode.string
        |> optional "Plans" decodePlans (Plans [])


decodePlans =
    Decode.map Plans <| Decode.list decodePlanNode

This code doesn’t pass muster either, resulting in this admonishing (but amusing) error message:

decodePlanNode is defined in terms of itself in a sneaky way, causing an infinite loop.

The following definitions depend directly on each other:

decodePlanNode
decodePlans

Something else is needed to break up the infinite loop. It turns out that the accepted solution to this problem (pointed out in Json.Decode documentation) is to wrap the recursive part in a call to Json.Decode.lazy which is a function that makes the decoder unroll lazily, thus sidestepping inifinite, universe-consuming expansion. We can apply it like this:

decodePlanNode = 
    decode PlanNode 
        |> required "Node Type" Decode.string
        |> optional "Plans" (Decode.lazy (\_ -> decodePlans)) (Plans [])


decodePlans =
    Decode.map Plans <| Decode.list decodePlanNode

We also need a change to main to make it work with the Plans type:

main : Html msg
main =
    let 
        output =
            case Decode.decodeString decodeJson json of
                Ok { executionTime, plan } ->
                    case plan.plans of 
                        Plans p -> toString <| List.map .nodeType p

                Err err ->
                    "Couldn't decode JSON"
    in
        text output

With these changes in place, there’s finally a little taste of success: the program compiles! But we’re not out of the woods yet, because we now get errors at runtime! The browser console shows this bad news:

Can't find variable: Elm

undefined is not an object (evaluating 'decoder.tag')

After going through the rabbit hole of GitHub issues, we learn that this is a telltale sign of a recursion problem, and to remedy that, additional sprinkling of Json.Decode.lazy is necessary:

decodePlanNode = 
    decode PlanNode 
        |> required "Node Type" Decode.string
        |> optional "Plans" (Decode.lazy (\_ -> decodePlans)) (Plans [])


decodePlans =
    Decode.map Plans <| Decode.list (Decode.lazy (\_ -> decodePlanNode))

And finally, armed with these decoders, the program outputs ["Hash"] as expected, and we can rejoice.

Summary

To summarise, there are three steps required to produce a recursive JSON decoder:

• Avoid recursion in the type definition by breaking up the single type alias into two parts
• Use Json.Decode.lazy to sidestep infinite recursion in the decoder definition
• Keep sprinkling Json.Decode.lazy until the runtime errors go away.

See and try out the final program in Ellie