Decoding a recursive multiway tree

Question

I'm working on a recursive tree of this type

type Node anyType
  = Leaf Id (Maybe anyType) Name
  | Tree Id (List (Node anyType)) Name

where

type Id
  = Id Int
  | Root

and I'm trying to decode a json of this kind into it

{
  "id": "root",
  "entries": [
    {
      "id": 1,
      "value": 0,
      "name": "New Entry"
    },
    {
      "id": 2,
      "entries": [
        {
          "id": 4,
          "value": 0,
          "name": "New Entry"
        }
      ],
      "name": "New Entry"
    }
  ],
  "name": "Budget"
}

To decode the Id type I'm using these decoders

rootDecoder =
(Decode.field "id" Decode.string)
    |> Decode.andThen
        (\str ->
            if str == "root" then
                (Decode.succeed Root)

            else
                Decode.fail <| "[exactMatch] tgt: " ++ "root" ++ " /= " ++ str
        )


intIdDecoder =
    Decode.map Id (Decode.field "id" Decode.int)


idDecoder =
    Decode.oneOf
        [ rootDecoder
        , intIdDecoder
        ]

To decode the tree structure i tried the following, using Json.Decode.Pipeline:

leafDecoder valueDecoder =
    Decode.succeed Leaf
        |> required "id" idDecoder
        |> required "value" valueDecoder
        |> required "name" Decode.string


treeDecoder valueDecoder =
    Decode.succeed Tree
        |> required "id" idDecoder
        |> required "entries"
            (Decode.list
                (Decode.lazy
                    (\_ ->
                        Decode.oneOf
                            [ leafDecoder valueDecoder
                            , treeDecoder valueDecoder
                            ]
                    )
                )
            )
        |> required "name" Decode.string

But when I try to decode the structure I get the following error:

The Json.Decode.oneOf at json.budget.entries[0] failed in the following 2 ways: (1) The Json.Decode.oneOf at json.id failed in the following 2 ways: (1) Problem with the given value: 1 Expecting an OBJECT with a field named `id` (2) Problem with the given value: 1 Expecting an OBJECT with a field named `id` (2) Problem with the given value: { "id": 1, "value": 0, "name": "New Entry" } Expecting an OBJECT with a field named `entries`

But I don't understand why since both the field id and entries are there, and yet it complains.

What am I doing wrong?

Answer 1

In your leafDecoder and treeDecoder you have the following lines:

leafDecoder valueDecoder =
    Decode.succeed Leaf
        |> required "id" idDecoder
        -- rest of function omitted...

treeDecoder valueDecoder =
    Decode.succeed Tree
        |> required "id" idDecoder
        -- rest of function omitted...

These will both pull out the value of the field id within the current object and pass this value on to idDecoder, which calls Decode.oneOf with rootDecoder and intIdDecoder.

However, in your rootDecoder and intIdDecoder you have the following:

rootDecoder =
    (Decode.field "id" Decode.string)
        |> Decode.andThen
            -- rest of function omitted...

intIdDecoder =
    Decode.map Id (Decode.field "id" Decode.int)

These decoders attempt to pull the value of a field named id from the current object. But you pass these functions the value of the id property, not an object containing this property.

These decoders would work if your ids were nested in objects that only contained id properties, for example:

{
  "id": {"id": "root"},
  "entries": [
    {
      "id": {"id": 1},
      "value": 0,
      "name": "New Entry"
    },
    ...

The fix is to remove the calls to Decode.field in rootDecoder and intIdDecoder, as these decoders already get passed the value of the id field:

rootDecoder =
    Decode.string
        |> Decode.andThen
            -- rest of function as before, and omitted for brevity...


intIdDecoder =
    Decode.map Id Decode.int

Answer 2

The problem is that both rootDecoder and intIdDecoder are defined as looking for a field named "id" in an object via Decode.field "id" .... Inside treeDecoder, you are first fetching the "id" field, so your decoder is valid for some JSON like this

// Not what you're looking for
{
  "id": {
    "id": ...
  },
  ...
}

You can fix this by removing the Decode.field "id" portion in those decoders:

rootDecoder = Decode.string
    |> Decode.andThen
        (\str ->
            if str == "root" then
                (Decode.succeed Root)

            else
                Decode.fail <| "[exactMatch] tgt: " ++ "root" ++ " /= " ++ str
        )


intIdDecoder =
    Decode.map Id Decode.int