Joachim Durchholz jo at durchholz.org
Wed Jul 8 17:27:09 UTC 2020

```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

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''
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
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
>
> 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
>
>         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:
>
>             /   \
>            /     \
>           /       \
>          v         v
>        Val 1     Val 1
>
>     and:
>
>             /   \
>            /     \
>            \    /
>             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:
>
>              /   \
>             /     \
>             \    /
>              v  v
>             /   \
>            /     \
>           /       \
>          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.
>
>
> _______________________________________________