Well, it makes a difference for me if I have twice the same subtree or sharing one subtree from several places. Later, I add some markers, thus, I know it is already processed or not.
Adding unique numbers and counting them makes sense if I know the result. If not then I don't know how to exploit it. But I may be tired too much already. :-(
Anyway, probably more imperative style would be a better option.
Thanks all,
Dušan
8. července 2020 18:13:34 SELČ, Viktor Dukhovni
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. _______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe Only members subscribed via the mailman list are allowed to post.