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 <ietf-dane@dukhovni.org> napsal:
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.