Does Elm allow circular references?

Question

Suppose two data types:

type alias Player = 
  { name : String
  , team : Team
  }

type alias Team =
  { name : String
  , players : List Player
  }

And this JSON:

{
  "players": [
    { "id": 100, "name": "Sam Bradford", "teamId": 200 },
    { "id": 101, "name": "Kyle Rudolph", "teamId": 200 },
    { "id": 102, "name": "Matthew Stafford", "teamId": 201 },
    { "id": 103, "name": "Marvin Jones Jr.", "teamId": 201 },
    { "id": 104, "name": "Golden Tate", "teamId": 201 },
  ],
  "teams": [
    { "id": 200, "name": "Minnesota Vikings" },
    { "id": 201, "name": "Detroit Lions" },
  ]
}

It's clear that this JSON can be decoded into non-null linked objects, and this can be determined by a JSON decoder as it is decoding the data. Is there a way to decode this JSON and create linked data structures? I'm not sure how to do this with purely immutable data structures, or if it is possible.

Answer 1

There is a good explanation of the recursive data types in Elm here.

If you try to compile your data types, you get the following error:

-- ALIAS PROBLEM ---------------------------------------------------------------

This type alias is part of a mutually recursive set of type aliases.

4|>type alias Player = 
5|>  { name : String
6|>  , team : Team
7|>  }

The following type aliases are mutually recursive:

    ┌─────┐
    │     V
    │    Player
    │     │
    │     V
    │    Team
    └─────┘

You need to convert at least one `type alias` into a `type`. This is a kind of
subtle distinction, so definitely read up on this before you make a fix:
<https://github.com/elm-lang/elm-compiler/blob/0.17.0/hints/recursive-alias.md>

You can also deal with this in another way. I prefer to resort to ID references, so e.g.

type alias ID = Int

type alias PlayerList = Dict ID PLayer
type alias TeamList = Dict ID Team

type alias Player = 
  { name : String
  , teamID : ID
  }

type alias Team =
  { name : String
  , players : List ID
  }

UPDATE: You also mention null references in your question. In the data types above the each player MUST have a team. If team is an optional field, I would define as follows:

type alias Player = 
  { name : String
  , teamID : Maybe ID
  }

For List and String types, you do not really need the Maybe type. Empty state for those is easier with [] (empty list) and "" (empty string).

PS: Another assumption is that you have a specific need to store the team player list in each team of your model. Because strictly speaking you do not need to: the list of players already has all the data needed to find out which players (if any) belong to team X. Please note that it is a lot of work (and can lead to nasty bugs) if you maintain the 2-way reference: if a player switches teams, you need to update 3 records (1 player + 2 team records).

Answer 2

With immutable data structures, it is not possible to create completely coupled hierarchies of values that reference each other in some circular fashion.

At its core, the problem can be illustrated in a few steps:

1. Create a child with Nothing for its parent field
2. Create a parent that points at the child
3. Update the child to point at the parent

Number 3 is impossible when you have immutable data structures, since a "modification" of the child means you create a new value, and the parent would still be pointing at that old value. If you then updated the parent, then you'd have to update the child again, ad infinitum.

I would recommend using a Dict of both Players and Teams, indexed by their respective ID for lookup purposes.