Hacker News Reader

Side question: How do you make DAGs immutable? Unlike trees where changing a node only requires a path copy of all ancestors, changing a node in a DAG has the potential to affect all other nodes. There are techniques such as using fat nodes[1] but I don't know of anyone using them in the real world.

[1] https://en.wikipedia.org/wiki/Persistent_data_structure#Fat_...

View on HN

You do need to trace all predecessors in this case, but in practice I don't think it's a serious problem. The kinds of graphs you'll get in UI are probably best thought of as trees with the possibility of shared resources (for example, all buttons of the same size might share the same background). On something like a theme change, I'd just rebuild the tree, although in theory you could be smarter and apply changes incrementally at a fine grain.

Reply on news.ycombinator.com