[Haskell-cafe] Test on identity?

[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.