logoalt Hacker News

pfdietztoday at 1:42 PM0 repliesview on HN

One place where this shows up is in parse trees. The grammar for a list of things may involve productions that look like list constructors. This, directly translated into a data structure, would give a very long chain of parse tree nodes dangling off to the right. It's a recursive data structure, but a very deep one for large lists, and traversing it recursively can use a lot of stack.

This can also be seen as an argument against building parse trees that way. Instead, have a node with an unbounded number of children, the elements of the list.