[Haskell-cafe] Test on identity?

[Joachim Durchholz]

Hi Dusan,

If you go imperative here, all code that builds on that data structure 
will be imperative as well, and you'll lose much of what makes Haskell 
interesting.

Try this mental model:

Step 1: Two objects are equal if all attributes are equal.
Just value equality here, i.e. assuming a language where you access all 
attributes (reference or direct) through an accessor like a.x, two 
objects a and b are equal if all accessor chains (e.g. x.y.z) that end 
in primitive values give you primitive-equality (e.g. a.x.y.z == 
b.x.y.z, and this works for all valid accessor chains).
(As you can see, equality is not a simple concept, and in languages 
where you have no primitives the definition becomes circular, but it's 
good enough for the model here.)

Step 2: Define "identity" to be "equality under change".
I.e. a and b are identical that if you assign to a.x.y.z, the same value 
will be found in b.x.y.z.
This "identity is equality under change" definition captures not just 
two objects at identical addresses, but also proxies, network objects, 
files, and whatever there is.

Step 3: Realize that if you have an immutable object, there is no 
relevant difference between equality and identity anymore. (You can make 
various formal statements about this.)

Step 4: So for an immutable object,
    A                                         B
   / \   is not just equal but identical to  / \
  /   \                                      \ /
x     x                                      x

Step 5: You want to be able to have
      A
     / \
    /   \
   x'    x''
after some updates.
That's not a problem! You "update" an object by creating a copy. Nothing 
prevents your code from creating an A(x',x'') tree when given an A(x,x) 
tree!


This train of thought helped my wrap my mind around some ideas in 
Haskell; I hope it will help you, and possibly other readers.
Everybody feel free to make it even more generally helpful :-)

Regards,
Jo


Am 08.07.20 um 18:42 schrieb Dušan Kolář:
> 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 at 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.
> 
> 
> _______________________________________________
> 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.
>