Help, my recursive Decoder caused a runtime exception!
The one runtime exception nearly every Elm developer will encounter sooner or later is this one, dealing with recursive JSON decoders:
Uncaught TypeError: Cannot read property ‘tag’ of undefined at runHelp
Context
Let’s say you are writing a decoder for a recursive structure:
With hypothetical JSON looking like this:
A first attempt
The most straightforward approach to this type of decoder, is to create a branch-decoder, a leaf-decoder and a tree-decoder, which would look something like this:
However, Elm is an eager language, and functions are evaluated as soon as all of their arguments are passed. In the above example, where decoders are simply values, we’re dealing with recursively defined values, and you can’t do that in an eager language. Elm will, of course, point this out in its usual, friendly manner.
Introducing laziness
After reading the linked document, you know you need to introduce laziness using — in this case — Json.Decode.lazy. You may be wondering where to put the call to lazy: should you lazily refer from decoder to branchDecoder, or should it be the other way around?
The slightly surprising answer is this:
There is no way to know for sure.
Elm orders its output based on how strongly connected different components are. In other words, a function that has more dependencies is more likely to appear later, a function that has fewer dependencies is more likely to appear earlier. In our case, that makes the most likely order leafDecoder -> branchDecoder -> decoder.
If we lazily refer to branchDecoder from decoder, this order doesn't change; and branchDecoder will still eagerly refer to decoder whose definition appears only later in the compiled code.
Let’s have a look at what that would compile to.
Sidenote: this is not quite what the compiled code looks like. I’ve stripped out the module-prefixes, partial application calls through the A* functions, and an Elm List really isn’t a JS array. However, it illustrates the core issue.
Notice that there’s only a single function definition in this whole thing - everything else is eagerly evaluated and has all of its argument available. After all, decoders are values! Note, also, that branchDecoder is defined before decoder is defined; yet it references decoder. Since only function declarations are hoisted to the top in JavaScript; the above code can't actually work! decoder will be undefined when branchDecoder is used.
A second attempt
Our second option is moving the lazy call so branchDecoder lazily refers to decoder instead:
Another look at the pseudo-compiled code shows that we have reached our goal, this time:
Now for the correct solution
The order in which compiled results appear in the output isn’t something you, while writing Elm code, should worry about. Figuring out the strongly connected components to figure out where the lazy should go, is not what you want to be thinking about.
Worse yet, slight changes to your decoders might result in the order changing in the compiled code!
The only real option when dealing with this type of recursion is to introduce lazy in both places:
This post was extracted from a document originally part of my Demystifying Decoders project. Learn more about that here:
