I ve been trying to make a functional graph. The graph I m making doesn t have loops, so it s a bit like a tree where some nodes can have more than one parent.
The problem is when updating. The usual way with a tree is to traverse down to the node to be updated, each step of the way creating a new node which is changed to point to a new child node, until the actual node to modify is reached who s data is then actually changed.
Taking this approach when some nodes have more than one parent breaks because you end up basically "splitting" the node. The node shared between two parents becomes two nodes with a parent each, one (the path you traversed to get to the node) having the new value and the other parent keeping a child with the old value.
So I instead tried storing the parent nodes inside each node, i.e. nodes know who their parents are.
This works, but there s a problem. If I update a node, I have to update its parents. But then for each of its parents, I don t only have to update their parents, but also their children, because their children store their parent node(s), and that parent node has now changed.
So to update one node value, I have to update every node in the graph.
The other idea I had was instead of storing the parent nodes in each node, just storing the "paths" to the parent nodes in each node. That way I shouldn t have to update the parent s children, as the "path" to the parent hasn t changed (even though the node itself has).
But perhaps there s a much better way of building a functional graph? Any ideas? I don t mind if it doesn t handle graphs with loops. I m coding in Haskell, but a non programming language description would be fine also.