Re: [Haskell-cafe] Test on identity?

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