On Wed, Jul 08, 2020 at 08:17:41AM +0200, Dušan Kolář wrote:
Nevertheless, I do even some transformations. Thus, I would like to know it is still a DAG, not adding, accidentally, a node.
Is there any way, if I have data like
data Ex = Val Int | Add Ex Ex
so that I can test that some value Val i === Val i ? I mean, the pointers go to the same data box? I could do that via some IORefs, AFAIK, but I don't think it is feasible. Maybe to tune the algorithm...
If, for the same "n", two "distinct" leaf nodes "Val n" are possible, in what sense is what you have still a DAG? If there's a difference between: Add / \ / \ / \ v v Val 1 Val 1 and: Add / \ / \ \ / v v Val 1 then perhaps the data model is flawed by failing to capture the distinguishing attributes of distinct leaf objects. And of course you might also have: Add / \ / \ \ / v v Add / \ / \ / \ v v Val 1 Val 2 So the most portable approach would be to assign a unique serial number all the nodes, both "Add", and "Val", and check that there's only path from the root to each distinct node (by serial number). Or, equivalently, a recursive enumeration of all the serial numbers contains no duplicates. -- Viktor.