Re: recursive equal, and firstDifference functions
On Wednesday, 20 March 2013 at 03:10:41 UTC, Jonathan M Davis wrote: The way == is defined is very clean and straightforward. There _are_ bugs which complicate things (e.g. http://d.puremagic.com/issues/show_bug.cgi?id=3789 ), but those can and will be fixed. The design itself is solid. Thanks for the detailed explanation. If 3789 covers strings, dynamic arrays and associative arrays and it were fixed then I agree, it is clean and straightforward. If I read it correctly with this fix it would change the current opEquals from semantically shallow to semantically deep by default. Semantically deep equality is comfortable to me, but I would imagine by now there is a fair amount of code that might rely on a false result from opEquals if the members (slices, associative arrays) are not bitwise the same. Thanks Dan
Re: recursive equal, and firstDifference functions
On Wednesday, March 20, 2013 12:47:38 Dan wrote: I would imagine by now there is a fair amount of code that might rely on a false result from opEquals if the members (slices, associative arrays) are not bitwise the same. I think that it's more likely that there's a lot of code that expects strings and the like to have their elements checked for equality when they're in a struct and is therefore buggy at present due to the fact that they aren't. As for AAs (which I forgot about), I don't remember what they're supposed to do with ==. They might just do a pointer comparison - or they may do a deeper comparison; I don't know. But the big problem there is that structs need to compare each of their members with ==, and that's not working properly at the moment, so that throws a major wrench in how == works. - Jonathan M Davis
recursive equal, and firstDifference functions
we need a std.algorithm.equalRecurse(T1,T2)(T1 a, T2 b) that
compares recursively a and b;
its behavior should be:
if opEqual is defined, call it
else, if its a range, call std.algorithm.equal (ie compare nb
elements, then each element for equality)
else, if it's a class/struct, make sure types are same and call
it recursively on each field.
else if it's a numerical type, call ==
else (is there an else?)
just as std.algorithm.equal, we should have
equalRecurse([1],[1.0]);
Currently, == works in a non-intuitive way, breaking principle
of least surprise:
struct A{ int[]b=[1]; }
void main(){
auto a1=A();
auto a2=A();
assert(a1!=a2);
}
we should have:
assert(equalRecurse(a1,a2));
What are your thoughts on those:
A)
Can we just extend std.algorithm.equal (which only works on
ranges) to arbitrary types instead of introducing a new function
equalRecurse ?
B)
Should == / opEqual behave like that (but it might be too late
to change)?
C)
in the example above, why assert(a1!=a2); but
assert(A.init==A.init); ?
D)
Additionally, we would need a sister function firstDifference(T1,
T2)(T1 a, T2 b) that finds the first difference among a and b.
How to represent that in a generic way is not clear (should for
example, find a particular field being different, etc). How about
a string output:
assert(firstDifference([1,2,3],[1,2,3]) == null);
assert(firstDifference([1,2,3],[1,3]) == a.length);
assert(firstDifference([1,2,3],[1,4,3]) == a[1]);
A a1; A a2; a1.x=1; a2.x=2;
assert(firstDifference(a1,a2) == a.x);
assert(firstDifference(a1,void) == typeid(a));
Both would be very useful for debugging.
Re: recursive equal, and firstDifference functions
On Tuesday, 19 March 2013 at 08:25:45 UTC, timotheecour wrote: we need a std.algorithm.equalRecurse(T1,T2)(T1 a, T2 b) that compares recursively a and b; its behavior should be: if opEqual is defined, call it else, if its a range, call std.algorithm.equal (ie compare nb elements, then each element for equality) else, if it's a class/struct, make sure types are same and call it recursively on each field. else if it's a numerical type, call == else (is there an else?) Not recursively, but how about something like this? 1) One type, one other - false 2) Both types - is(A == B) 3) Both symbols __traits(isSame) - true 4) A symbol __traits(compiles, (A.opEquals(B))) - A.opEquals(B) 5) B symbol __traits(compiles, (B.opEquals(A))) - B.opEquals(A) 6) A symbol __traits(compiles, (A.equals(B))) - A.equals(B) 7) B symbol __traits(compiles, (B.equals(A))) - B.equals(A) 8) Both symbols or values __traits(compiles, A == B) - A == B 9) assert(0)
Re: recursive equal, and firstDifference functions
On Tuesday, March 19, 2013 09:25:43 timotheecour wrote: we need a std.algorithm.equalRecurse(T1,T2)(T1 a, T2 b) that compares recursively a and b; its behavior should be: if opEqual is defined, call it else, if its a range, call std.algorithm.equal (ie compare nb elements, then each element for equality) else, if it's a class/struct, make sure types are same and call it recursively on each field. else if it's a numerical type, call == else (is there an else?) just as std.algorithm.equal, we should have equalRecurse([1],[1.0]); If you want recursive equal, then do equal!equal. Granted, that's only one level of recursion, but how many levels deep are you really going to have your ranges? And you have to get to == eventually anyway in order to compare the deepest elements. Going beyond a range of ranges is likely to be quite rare, and when it does happen, you can simply nest equal as many times as you need. - Jonathan M Davis
Re: recursive equal, and firstDifference functions
On Tuesday, 19 March 2013 at 10:08:43 UTC, Jonathan M Davis wrote: On Tuesday, March 19, 2013 09:25:43 timotheecour wrote: we need a std.algorithm.equalRecurse(T1,T2)(T1 a, T2 b) that compares recursively a and b; its behavior should be: if opEqual is defined, call it else, if its a range, call std.algorithm.equal (ie compare nb elements, then each element for equality) else, if it's a class/struct, make sure types are same and call it recursively on each field. else if it's a numerical type, call == else (is there an else?) just as std.algorithm.equal, we should have equalRecurse([1],[1.0]); If you want recursive equal, then do equal!equal. Granted, that's only one level of recursion, but how many levels deep are you really going to have your ranges? And you have to get to == eventually anyway in order to compare the deepest elements. Going beyond a range of ranges is likely to be quite rare, and when it does happen, you can simply nest equal as many times as you need. - Jonathan M Davis equal!equal(RoR1, RoR2) That looks cute, but I think it says something about how powerful and expressive D can be, while being compile-time optimized. It's those little things that still amaze me about D.
Re: recursive equal, and firstDifference functions
Jonathan M Davis: Going beyond a range of ranges is likely to be quite rare, I agree. and when it does happen, you can simply nest equal as many times as you need. A similar function seems useful for Phobos because it's automatic, you don't need to tell it how many levels there are. Bye, bearophile
Re: recursive equal, and firstDifference functions
On Tuesday, 19 March 2013 at 11:46:14 UTC, monarch_dodra wrote:
On Tuesday, 19 March 2013 at 10:08:43 UTC, Jonathan M Davis
wrote:
On Tuesday, March 19, 2013 09:25:43 timotheecour wrote:
we need a std.algorithm.equalRecurse(T1,T2)(T1 a, T2 b) that
compares recursively a and b;
its behavior should be:
if opEqual is defined, call it
else, if its a range, call std.algorithm.equal (ie compare nb
elements, then each element for equality)
else, if it's a class/struct, make sure types are same and
call
it recursively on each field.
else if it's a numerical type, call ==
else (is there an else?)
just as std.algorithm.equal, we should have
equalRecurse([1],[1.0]);
If you want recursive equal, then do equal!equal. Granted,
that's only one
level of recursion, but how many levels deep are you really
going to have your
ranges? And you have to get to == eventually anyway in order
to compare the
deepest elements. Going beyond a range of ranges is likely to
be quite rare,
and when it does happen, you can simply nest equal as many
times as you need.
- Jonathan M Davis
equal!equal(RoR1, RoR2)
That looks cute, but I think it says something about how
powerful and expressive D can be, while being compile-time
optimized. It's those little things that still amaze me about D.
and then:
template NumDimensions (T) {
static if(is(ElementType!T == void))
const NumDimensions = 0;
else
const NumDimensions = 1 + NumDimensions!(ElementType!T);
}
bool rec_equal(R0, R1)(R0 r0, R1 r1)
if(NumDimensions!R0 == NumDimensions!R1)
{
mixin(return ~ replicate(equal!, NumDimensions!(R0)-1) ~
equal(r0, r1););
}
obviously it requires some more checks, but it works nicely
(except if you feed it two integer literals, in which case the
compiler throws an out of memory error!).
Re: recursive equal, and firstDifference functions
On Tuesday, 19 March 2013 at 12:16:54 UTC, John Colvin wrote:
On Tuesday, 19 March 2013 at 11:46:14 UTC, monarch_dodra wrote:
On Tuesday, 19 March 2013 at 10:08:43 UTC, Jonathan M Davis
wrote:
On Tuesday, March 19, 2013 09:25:43 timotheecour wrote:
we need a std.algorithm.equalRecurse(T1,T2)(T1 a, T2 b) that
compares recursively a and b;
its behavior should be:
if opEqual is defined, call it
else, if its a range, call std.algorithm.equal (ie compare nb
elements, then each element for equality)
else, if it's a class/struct, make sure types are same and
call
it recursively on each field.
else if it's a numerical type, call ==
else (is there an else?)
just as std.algorithm.equal, we should have
equalRecurse([1],[1.0]);
If you want recursive equal, then do equal!equal. Granted,
that's only one
level of recursion, but how many levels deep are you really
going to have your
ranges? And you have to get to == eventually anyway in order
to compare the
deepest elements. Going beyond a range of ranges is likely to
be quite rare,
and when it does happen, you can simply nest equal as many
times as you need.
- Jonathan M Davis
equal!equal(RoR1, RoR2)
That looks cute, but I think it says something about how
powerful and expressive D can be, while being compile-time
optimized. It's those little things that still amaze me about
D.
and then:
template NumDimensions (T) {
static if(is(ElementType!T == void))
const NumDimensions = 0;
else
const NumDimensions = 1 + NumDimensions!(ElementType!T);
}
bool rec_equal(R0, R1)(R0 r0, R1 r1)
if(NumDimensions!R0 == NumDimensions!R1)
{
mixin(return ~ replicate(equal!, NumDimensions!(R0)-1) ~
equal(r0, r1););
}
obviously it requires some more checks, but it works nicely
(except if you feed it two integer literals, in which case the
compiler throws an out of memory error!).
correction:
bool rec_equal(R0, R1)(R0 r0, R1 r1)
if(NumDimensions!R0 == NumDimensions!R1)
{
static if(NumDimensions!R0 == 0)
return r0 == r1;
else
mixin(return ~ replicate(equal!, NumDimensions!(R0)-1) ~
equal(r0, r1););
}
Re: recursive equal, and firstDifference functions
On Tuesday, 19 March 2013 at 12:16:54 UTC, John Colvin wrote: (except if you feed it two integer literals, in which case the compiler throws an out of memory error!). Which is a legitimate error, seeing as -1 as a size_t is size_t.max which meant replicate was requesting size_t.max * int.sizeof bytes. See my correction to the code in my other reply.
Re: recursive equal, and firstDifference functions
On Tuesday, 19 March 2013 at 12:11:50 UTC, bearophile wrote: Jonathan M Davis: Going beyond a range of ranges is likely to be quite rare, I agree. and when it does happen, you can simply nest equal as many times as you need. A similar function seems useful for Phobos because it's automatic, you don't need to tell it how many levels there are. Bye, bearophile But the compiler can't tell how many levels deep you want to go. There are legitimate cases of Range of Stuff where Stuff just so happens to be a range, but you don't want range comparison. For example: class MyClassRange; MyClassRange a, b; SuperEqual(a, b); //? I think using equal!equal is not that much more verbose, but safer/explicit.
Re: recursive equal, and firstDifference functions
On Tuesday, 19 March 2013 at 12:34:04 UTC, monarch_dodra wrote: On Tuesday, 19 March 2013 at 12:11:50 UTC, bearophile wrote: Jonathan M Davis: Going beyond a range of ranges is likely to be quite rare, I agree. and when it does happen, you can simply nest equal as many times as you need. A similar function seems useful for Phobos because it's automatic, you don't need to tell it how many levels there are. Bye, bearophile But the compiler can't tell how many levels deep you want to go. There are legitimate cases of Range of Stuff where Stuff just so happens to be a range, but you don't want range comparison. For example: class MyClassRange; MyClassRange a, b; SuperEqual(a, b); //? I think using equal!equal is not that much more verbose, but safer/explicit. I think if your calling a recursive version of equal, then you assume it will go as deep as possible. If you want control as to how deep, then you can either use equal manually, or there could be a maximum depth parameter to the recursive equal.
Re: recursive equal, and firstDifference functions
On Tuesday, 19 March 2013 at 12:36:34 UTC, John Colvin wrote:
On Tuesday, 19 March 2013 at 12:34:04 UTC, monarch_dodra wrote:
On Tuesday, 19 March 2013 at 12:11:50 UTC, bearophile wrote:
Jonathan M Davis:
Going beyond a range of ranges is likely to be quite rare,
I agree.
and when it does happen, you can simply nest equal as many
times as you need.
A similar function seems useful for Phobos because it's
automatic, you don't need to tell it how many levels there
are.
Bye,
bearophile
But the compiler can't tell how many levels deep you want to
go. There are legitimate cases of Range of Stuff where Stuff
just so happens to be a range, but you don't want range
comparison.
For example:
class MyClassRange;
MyClassRange a, b;
SuperEqual(a, b); //?
I think using equal!equal is not that much more verbose, but
safer/explicit.
I think if your calling a recursive version of equal, then you
assume it will go as deep as possible. If you want control as
to how deep, then you can either use equal manually, or there
could be a maximum depth parameter to the recursive equal.
i.e.
import std.array : replicate;
import std.algorithm : min;
import std.range : ElementType, equal;
bool rec_equal(size_t max_depth = size_t.max, R0, R1)(R0 r0, R1
r1)
if(NumDims!R0 == NumDims!R1)
{
static if(NumDims!R0 == 0 || max_depth == 0)
return r0 == r1;
else {
mixin(return ~
replicate(equal!, min(max_depth-1, NumDims!(R0)-1))
~
equal(r0, r1);
);
}
}
template NumDims (T) {
static if(is(ElementType!T == void))
const NumDims = 0;
else
const NumDims = 1 + NumDims!(ElementType!T);
}
Re: recursive equal, and firstDifference functions
I think none of you got the point of equalRecurse, so let me clarify. equalRecurse should work on any type, not just inputRanges, see my example in the OT with a struct containing an array: currently std.algorithm.equal has isInputRange conditions on the arguments. So, yes, it can go deep in practice (struct containing an array of struct, etc), unlike nesting ranges where it's not common in practice. I wouldn't think it's that hard to do, at least for the common cases in practice. Maybe what was confusing is that I wanted it in std.algorithm, but all functions in there operate on ranges, so maybe somewhere else, but I don't see a relevant package. Maybe a new std.algorithm2 for non-ranges? Also, the OT's firstDifference would go there too, and I have a recursive (to specified level) toStringRecurse that would belong there too.
Re: recursive equal, and firstDifference functions
On Tuesday, March 19, 2013 18:08:53 timotheecour wrote: I think none of you got the point of equalRecurse, so let me clarify. equalRecurse should work on any type, not just inputRanges, Which is fundamentally wrong. == and equal are two very different operations, even if their intent may be similar. And aside from ranges, unless you're creating your own function for checking for some other type of equality beyond what ==, is, or equal check for, all you'd ever use is == or is anyway. So, if you want to compare ranges with equal, then use equal. Otherwise use ==. Expecting the compiler to automagically figure out how to compare two types for you is just begging for trouble (especially when you add stuff like alias this into the mix). - Jonathan M Davis
Re: recursive equal, and firstDifference functions
somewhere else, but I don't see a relevant package. Maybe a new std.algorithm2 for non-ranges? Also, the OT's firstDifference would go there too, and I have a recursive (to specified level) toStringRecurse that would belong there too. Also, I'd add to that list copyRecurse and some more, that operate on arbitrary types, not just ranges, so we have: equalRecurse copyRecurse (deep copy) toStringRecurse firstDifference (see OT) toHashRecurse (should compare equal with a data structure serialized and then deserialized via a serialization function, eg std.orange) I'm sure there's more. that seems a starting point for a new package that operates on any type recursively (not just ranges), no? std.deep?std.recurse? Some of those could have a depth level compile time parameter that stops recursion at that level, which would be infinity by default.
Re: recursive equal, and firstDifference functions
On Tuesday, March 19, 2013 18:26:16 timotheecour wrote: somewhere else, but I don't see a relevant package. Maybe a new std.algorithm2 for non-ranges? Also, the OT's firstDifference would go there too, and I have a recursive (to specified level) toStringRecurse that would belong there too. Also, I'd add to that list copyRecurse and some more, that operate on arbitrary types, not just ranges, so we have: equalRecurse copyRecurse (deep copy) toStringRecurse firstDifference (see OT) toHashRecurse (should compare equal with a data structure serialized and then deserialized via a serialization function, eg std.orange) I'm sure there's more. that seems a starting point for a new package that operates on any type recursively (not just ranges), no? std.deep?std.recurse? Some of those could have a depth level compile time parameter that stops recursion at that level, which would be infinity by default. And how do you even have the concept of recursion without some sort of range or container to recursively iterate through? - Jonathan M Davis
Re: recursive equal, and firstDifference functions
On Tue, Mar 19, 2013 at 01:48:43PM -0400, Jonathan M Davis wrote:
On Tuesday, March 19, 2013 18:26:16 timotheecour wrote:
somewhere else, but I don't see a relevant package. Maybe a new
std.algorithm2 for non-ranges?
Also, the OT's firstDifference would go there too, and I have a
recursive (to specified level) toStringRecurse that would
belong there too.
Also, I'd add to that list copyRecurse and some more, that
operate on arbitrary types, not just ranges, so we have:
equalRecurse
copyRecurse (deep copy)
toStringRecurse
firstDifference (see OT)
toHashRecurse (should compare equal with a data structure
serialized and then deserialized via a serialization function, eg
std.orange)
I'm sure there's more.
that seems a starting point for a new package that operates on any
type recursively (not just ranges), no? std.deep?std.recurse? Some
of those could have a depth level compile time parameter that stops
recursion at that level, which would be infinity by default.
And how do you even have the concept of recursion without some sort of
range or container to recursively iterate through?
[...]
One can iterate over every member of a struct/class and recursively
invoke equalRecurse on them. Something like this:
bool recursiveEqual(T)(T a, T b) {
static if (isAtomic!T) {
return a == b;
} else {
foreach (attr; __traits(getAllMembers, T)) {
// TBD: need to skip stuff like member
// functions or internal stuff like
// compiler-generated attributes, hidden
// context ptrs, etc.
alias attr1 = __traits(getMember, a, attr);
alias attr2 = __traits(getMember, b, attr);
if (!recursiveEqual(attr, attr2))
return false;
}
}
return true;
}
T
--
The best way to destroy a cause is to defend it poorly.
Re: recursive equal, and firstDifference functions
And how do you even have the concept of recursion without some
sort of range or container to recursively iterate through?
It's not hard: I've done it for a serialization library I've been
working on (which has some advantages over std.orange, such as
serializing to json/binary etc. more on this later), as well as
for my toStringRecurse: it works on any data type roughly as
follows:
auto equalRecurse(T)(T a) {
static if isAssociativeArray!(T)) {
}
else static if(isArray!(T)) {
}
else static if(is(T == struct) ){
foreach(i, member; a.tupleof) {
...
}
else static if...
}
Expecting the compiler to automagically figure out how to
compare two types for you is just begging for trouble
I beg to differ. I like to be as lazy as possible when writing
user code (as opposed to library code). The compiler can do a lot
of stuff automagically in D thanks to CT reflection. I didn't run
into problems when using the serialization on rather complex
nested objects.
Re: recursive equal, and firstDifference functions
On Tuesday, 19 March 2013 at 08:25:45 UTC, timotheecour wrote:
we need a std.algorithm.equalRecurse(T1,T2)(T1 a, T2 b) that
compares recursively a and b;
its behavior should be:
if opEqual is defined, call it
The problem is, Object defines opEqual as bool opEquals(Object
o){return this is o;}, so that ruins a lot of class comparisons.
An example implementation of what I think you're getting at:
http://dpaste.dzfl.pl/a7889060
bool deep_equal(T)(T a, T b) {
static if(isInputRange!T)
return rec_equal(a, b);
else static if(__traits(isScalar, T) /*|| __traits(hasMember, T,
opEquals)*/)
return a == b;
else {
foreach(i, a_field; a.tupleof)
if(!deep_equal(a_field, b.tupleof[i]))
return false;
return true;
}
}
bool rec_equal(size_t max_depth = size_t.max, R0, R1)(R0 r0, R1
r1)
if(NumDims!R0 == NumDims!R1)
{
static if(NumDims!R0 == 0 || max_depth == 0)
return r0 == r1;
else {
mixin(return ~
replicate(equal!, min(max_depth-1, NumDims!(R0)-1)) ~
equal(r0, r1);
);
}
}
template NumDims (T) {
static if(is(ElementType!T == void))
const NumDims = 0;
else
const NumDims = 1 + NumDims!(ElementType!T);
}
Re: recursive equal, and firstDifference functions
On Tuesday, March 19, 2013 11:12:38 H. S. Teoh wrote:
On Tue, Mar 19, 2013 at 01:48:43PM -0400, Jonathan M Davis wrote:
On Tuesday, March 19, 2013 18:26:16 timotheecour wrote:
somewhere else, but I don't see a relevant package. Maybe a new
std.algorithm2 for non-ranges?
Also, the OT's firstDifference would go there too, and I have a
recursive (to specified level) toStringRecurse that would
belong there too.
Also, I'd add to that list copyRecurse and some more, that
operate on arbitrary types, not just ranges, so we have:
equalRecurse
copyRecurse (deep copy)
toStringRecurse
firstDifference (see OT)
toHashRecurse (should compare equal with a data structure
serialized and then deserialized via a serialization function, eg
std.orange)
I'm sure there's more.
that seems a starting point for a new package that operates on any
type recursively (not just ranges), no? std.deep?std.recurse? Some
of those could have a depth level compile time parameter that stops
recursion at that level, which would be infinity by default.
And how do you even have the concept of recursion without some sort of
range or container to recursively iterate through?
[...]
One can iterate over every member of a struct/class and recursively
invoke equalRecurse on them. Something like this:
bool recursiveEqual(T)(T a, T b) {
static if (isAtomic!T) {
return a == b;
} else {
foreach (attr; __traits(getAllMembers, T)) {
// TBD: need to skip stuff like member
// functions or internal stuff like
// compiler-generated attributes, hidden
// context ptrs, etc.
alias attr1 = __traits(getMember, a, attr);
alias attr2 = __traits(getMember, b, attr);
if (!recursiveEqual(attr, attr2))
return false;
}
}
return true;
}
True, but that's completely different from what equal does, and it would be
very dangerous IMHO. opEquals is supposed to be handling comparing types
recursively like that. Deciding on your own that a type's member variables
should be compared with equal instead of == risk doing some nasty things to
the semantics of the types that you're dealing with. If a type's member
variables need to be compared with equal, then its opEquals should do that.
equal is for handling the case where you're comparing two arbitrary ranges of
elements. You don't care what the types of the ranges are. You're comparing
the elements, not the ranges. You would only need to recursively compare the
elements with anything other than == if they were ranges, and you wanted to
ultimately compare the elements of the deepest ranges. == already exists to
compare the elements themselves recursively.
I'd strongly argue that a function like the one that you just gave is an
extremely bad idea. It's trying to implement == for a type. Let the type define
that for itself like it's supposed to.
- jonathan M Davis
Re: recursive equal, and firstDifference functions
On Tuesday, 19 March 2013 at 17:08:54 UTC, timotheecour wrote: I think none of you got the point of equalRecurse, so let me clarify. I think I understand what you are after and I like the idea. I've got a few: -typesDeepEqual -typesDeepCmp -deepHash Have a look at: https://github.com/patefacio/d-help/blob/master/d-help/opmix/mix.d Thanks Dan
Re: recursive equal, and firstDifference functions
On Tuesday, March 19, 2013 19:13:14 timotheecour wrote:
And how do you even have the concept of recursion without some
sort of range or container to recursively iterate through?
It's not hard: I've done it for a serialization library I've been
working on (which has some advantages over std.orange, such as
serializing to json/binary etc. more on this later), as well as
for my toStringRecurse: it works on any data type roughly as
follows:
auto equalRecurse(T)(T a) {
static if isAssociativeArray!(T)) {
}
else static if(isArray!(T)) {
}
else static if(is(T == struct) ){
foreach(i, member; a.tupleof) {
...
}
else static if...
}
Expecting the compiler to automagically figure out how to
compare two types for you is just begging for trouble
I beg to differ. I like to be as lazy as possible when writing
user code (as opposed to library code). The compiler can do a lot
of stuff automagically in D thanks to CT reflection. I didn't run
into problems when using the serialization on rather complex
nested objects.
Serialization is completely different from comparing the equality of two
objects. That's opEquals' job. It deals with recursive comparisons like you're
describing here just fine. There's no reason to define that externallly to the
type. equal's job, on the other hand, is to compare the elements of two ranges
- _not_ the ranges themselves - which is fundamentally different from ==.
- Jonathan M Davis
Re: recursive equal, and firstDifference functions
I think I understand what you are after and I like the idea. I've got a few: -typesDeepEqual -typesDeepCmp -deepHash approxEqualRecurse could also be useful for numerical applications (same as equalRecurse, except uses approxEqual for floating point comparisons) https://github.com/patefacio/d-help/blob/master/d-help/opmix/mix.d Thanks for the link, I'll take a look.
Re: recursive equal, and firstDifference functions
That's opEquals' job. It deals with recursive comparisons like
you're describing here just fine.
Except the functionality is very different, as opEquals is blind
to range semantics. I want equalRecurse to work as follows:
struct A{ int[]b=[1]; }
void main(){
auto a1=A();
auto a2=A();
assert(a1!=a2); //opEquals says it's different
assert(equalRecurse(a1,a2)); //equalRecurse says it's the same
// assert(equal(a1,a2)); //equal doesn't compile, only works for
ranges.
}
There's no reason to define that externallly to the type.
Yes there is: it can be done automagically to work on vast
majority of cases (see what several ppl have posted), and it
avoids overly redundant boilerplate code. In my example here, I
don't want to redefine an opEquals to make the assert(a1==a2);
above pass, because:
-it's boilerplate
-equalRecurse has different semantics anyways
-meaning of equalRecurse should be clear to anyone.
Re: recursive equal, and firstDifference functions
On Tuesday, March 19, 2013 21:13:21 timotheecour wrote: That's opEquals' job. It deals with recursive comparisons like you're describing here just fine. Except the functionality is very different, as opEquals is blind to range semantics. opEquals defines equality however it chooses to define equality. It's trivial for it to use equal on any member variables which are ranges. opEquals is the way that the language defines equality. equal is only necessary when trying to compare the elements of two ranges rather than compare two objects. == is what is supposed to be used to compare two objects. You seem to basically be trying to work your way around the language rather than using it the way it's designed, which is just asking for trouble. And if the problem is that you don't want to write boilerplate code, and you want to define an opEquals that compares ranges with equal and everything else with ==, then it would be fairly trivial to write a string or template mixin to mix in opEquals for you. If you avoid defining == properly, then you're going to have problems wiith all kinds of stuff which assumes that == is used to define equality (including stuff like the built-in AAs). Avoiding boilerplate code is poor excuse to give your types odd semantics by not defining opEquals and using an external function to compare for equality. - Jonathan M Davis
Re: recursive equal, and firstDifference functions
On Tuesday, March 19, 2013 20:36:09 Dan wrote: On Tuesday, 19 March 2013 at 17:08:54 UTC, timotheecour wrote: I think none of you got the point of equalRecurse, so let me clarify. I think I understand what you are after and I like the idea. I've got a few: -typesDeepEqual -typesDeepCmp -deepHash Those are what opEquals, opCmp, and toHash are for. It might make sense to define mixins which implement them for you (dealing with whatever recursive semantics are necessary), but using external functions for those just isn't going to fly. The language and standard library are designed around them being part of the types themselves. Stuff like AAs won't work if those functions aren't defined on the types themselves. - Jonathan M Davis
Re: recursive equal, and firstDifference functions
On Tuesday, 19 March 2013 at 20:28:09 UTC, Jonathan M Davis wrote: Those are what opEquals, opCmp, and toHash are for. It might make sense to define mixins which implement them for you (dealing with whatever recursive semantics are necessary), but using external functions for those just isn't going to fly. Understand the sentiment. But you can easily have those external functions call the member equivalents if they exist, and if not still proceed and work. This is what they do, in fact. For instance, it is nice to have the mixin for opCmp that actually calls member opCmp if they exist. This opens the door a bit. It allows you to have a reasonable opCmp for a type with a member that has none. The same approach can be used for dup/gdup - which we have discussed a few times now. The language and standard library are designed around them being part of the types themselves. Stuff like AAs won't work if those functions aren't defined on the types themselves. Sorry, I don't understand the last statement.
Re: recursive equal, and firstDifference functions
On Tuesday, March 19, 2013 21:50:55 Dan wrote: On Tuesday, 19 March 2013 at 20:28:09 UTC, Jonathan M Davis wrote: The language and standard library are designed around them being part of the types themselves. Stuff like AAs won't work if those functions aren't defined on the types themselves. Sorry, I don't understand the last statement. Lots of stuff uses ==, toHash, etc. That's the way the language is designed. Defining your types without defining those properly just isn't going to work for a _lot_ of stuff. Creating an external function to compare objects or generate hashes or anything like that is just going to cause problems, because only your stuff would use it. The built-in stuff wouldn't, and the standard library wouldn't. For instance, AAs require that opEquals and toHash be defined, and no matter how clever your external functions for comparing objects or generating hashes are, they're not going to work with the built-in AAs. Any type which is going to work with the built-in AAs must define opEquals and toHash. So, if the problem is boilerplate code, mixins can be used for opEquals, opCmp, etc. in order to define those for you, but creating external functions to do those same operations is not how the language was designed and isn't how anything is going to expect types to work. Anything that wants to be comparable, should define ==. Anything that wants to be hashable should define toHash. Etc. Something like equalRecurse ultimately really makes no sense at all. - Jonathan M Davis
Re: recursive equal, and firstDifference functions
On Tuesday, 19 March 2013 at 21:11:12 UTC, Jonathan M Davis wrote:
Lots of stuff uses ==, toHash, etc. That's the way the language
is designed.
Agreed
Defining your types without defining those properly just isn't
going to work for
a _lot_ of stuff. Creating an external function to compare
objects or generate
hashes or anything like that is just going to cause problems,
because only
your stuff would use it.
Ok - you are making strong statement and I don't see why it is
the case.
Here is an example that does work for hashing.
Note: R implements its own hash and just prints to show nothing
up the sleeve.
Other classes (S,T) have no toHash implemented directly at all -
yet you can see u1 and u3 resolve to the same hash and u2 a
different, as you would expect.
-
import std.stdio;
import opmix.mix;
import pprint.pp;
struct R {
string r;
hash_t toHash() const nothrow {
try {
writeln(toHash called on r);
} catch(Exception) {
}
return typeid(string).getHash(r);
}
}
struct S {
R r;
string s;
string[int] si;
}
struct T {
S s;
}
struct U {
mixin ToHash;
T t;
}
void main() {
U u1 = U(T(S(R(a), foo, [1:goo])));
U u2 = U(T(S(R(a), foo.idup)));
U u3 = U(T(S(R(a), foo.idup, [1:goo.idup])));
writeln(deepHash(u1));
writeln(deepHash(u2));
writeln(deepHash(u3));
writeln(pp(u1));
int[U] aa;
aa[u1] = 100;
writeln(Is u1 in aa , u1 in aa);
writeln(Is u2 in aa , u2 in aa);
aa[u2] = 100;
writeln(Is u2 in now aa , u2 in aa);
}
--- OUTPUT --
toHash called on r
614624
toHash called on r
582446
toHash called on r
614624
{
(U).t = {
(T).s = {
(S).r = {
(R).r = a
}
(S).s = foo
(S).si = {
(K(1)[0] =
V(goo)),
}
}
}
}
toHash called on r
toHash called on r
Is u1 in aa 7F2C7E556FC0
toHash called on r
Is u2 in aa null
toHash called on r
toHash called on r
Is u2 in now aa 7F2C7E556F40
--
The built-in stuff wouldn't, and the standard library
wouldn't. For instance, AAs require that opEquals and toHash be
defined, and no
matter how clever your external functions for comparing objects
or generating
hashes are, they're not going to work with the built-in AAs.
Any type which is
going to work with the built-in AAs must define opEquals and
toHash.
The above works with the built-in AAs.
Please offer an example.
Thanks
Dan
Re: recursive equal, and firstDifference functions
On Tuesday, March 19, 2013 22:43:10 Dan wrote: The above works with the built-in AAs. Please offer an example. It works because the outer type defines toHash. Without toHash, the built-in AAs won't work. If you're dealing with member variables which don't have toHash, then doing something like you did is an option, but the outer type still needs toHash, and if any of the member variables define an opEquals but not a toHash, then you risk having your hash change when a member variable changes even when the new value of the member variable is considered equal to the old one (e.g. because a cached value or some other member variable in that type is not considered to be part of the equality of an object but _would_ be considered to be part of the hash if you use reflection to generate a hash from all of that type's member variables). So, using reflection to generate hashes for arbitrary types can be risky. Whether it works on not depends on how those types are defined and what you're doing with them. But the main problem that I'm pointing out is that you can't define your own, non-standard functions for equality or hashing or whatever and expect your types to play nicely with other stuff. If your stuff is wrapped in types that do define the proper functions for that (like in your example), then it can work, but the types which were wrapped won't play nice outside of the wrapper. - Jonathan M Davis
Re: recursive equal, and firstDifference functions
On Tuesday, 19 March 2013 at 23:13:19 UTC, Jonathan M Davis wrote: On Tuesday, March 19, 2013 22:43:10 Dan wrote: The above works with the built-in AAs. Please offer an example. It works because the outer type defines toHash. Without toHash, the built-in AAs won't work. If you're dealing with member variables which don't have toHash, then doing something like you did is an option, but the outer type still needs toHash, and if any of the member variables define an opEquals but not a toHash, then you risk having your hash change when a member variable changes even when the new value of the member variable is considered equal to the old one (e.g. because a cached value or some other member variable in that type is not considered to be part of the equality of an object but _would_ be considered to be part of the hash if you use reflection to generate a hash from all of that type's member variables). So, using reflection to generate hashes for arbitrary types can be risky. Whether it works on not depends on how those types are defined and what you're doing with them. For hashing it is not foolproof as you mentioned. It is important to understand that opEquals and toHash should share the same semantics (i.e. if they are equal they should hash the same). But, in general, when you control the code you don't need toHash or opEquals at every level of composition and it will still work fine (compile-time recursively) as a key in a AA. But the main problem that I'm pointing out is that you can't define your own, non-standard functions for equality or hashing or whatever and expect your types to play nicely with other stuff. If your stuff is wrapped in types that do define the proper functions for that (like in your example), then it can work, but the types which were wrapped won't play nice outside of the wrapper. This is true, but then my code is by definition not standard. However, theoretically, the language writers could. For example, any '==' could be lowered to a 'standard' function, probably better named 'intancesDeepEqual(a,b)' and that function could use reflection to provide equal when not available else call opEquals if it is available. Similar with opCmp, dup, idup, ... In other words, in the vein of the original poster, why not allow all of these nice goodies (equality comparison, opCmp comparison, dup) without requiring boilerplate code while still honoring/using it when it is provided. Thanks Dan
Re: recursive equal, and firstDifference functions
On Wednesday, March 20, 2013 01:17:13 Dan wrote: This is true, but then my code is by definition not standard. However, theoretically, the language writers could. For example, any '==' could be lowered to a 'standard' function, probably better named 'intancesDeepEqual(a,b)' and that function could use reflection to provide equal when not available else call opEquals if it is available. Similar with opCmp, dup, idup, ... In other words, in the vein of the original poster, why not allow all of these nice goodies (equality comparison, opCmp comparison, dup) without requiring boilerplate code while still honoring/using it when it is provided. There _are_ defaults for ==, and it really does quite a lot for you (e.g. recursively using == on each of a type's member variables), so you don't always have to define opEquals, but as soon as you have a layer of indirection (aside from arrays), you do have to define opEquals, or you'll generally end up checking for reference/pointer equality rather than equality of the actual objects. And in some cases, that's exactly the right thing to do. In others, it's not. It all depends on the context. As for comparing ranges, it would actually be very bad for performance if they defaulted to what equal does (particularly with regards to strings), and the language really doesn't do much to support ranges directly. Aside from foreach, they're completely a library construct. And really, equal exists with the idea that ranges of different types (but the same element type) can be compared, which isn't what you're generally trying to do with opEquals at all. If you want to avoid boilerplate, then use mixins. It should be fairly trivial to define a mixin such that you can do something like mixin(defineOpEquals!(typeof(this))); which defines an opEquals which does deep comparison. But also remember that what is necessary for deep comparison often depends on the types being compared (e.g. a range may or may not require equal to get the comparison that you want), so while it may be possible to define a mixin which creates an opEquals which will work in most situations, there are plenty where it won't. For instance, given that the standard library supports ranges, it's likely that something like defineOpEquals would know about them and do what is most likely to be the correct thing for them, but if ranges weren't part of the standard library, thhen defineOpEquals wouldn't know about them and couldn't handle them properly. The same will be true for any user-defined type that requires a particular idiom in order to be compared correctly. - Jonathan M Davis
Re: recursive equal, and firstDifference functions
On Wed, Mar 20, 2013 at 01:17:13AM +0100, Dan wrote: On Tuesday, 19 March 2013 at 23:13:19 UTC, Jonathan M Davis wrote: [...] But the main problem that I'm pointing out is that you can't define your own, non-standard functions for equality or hashing or whatever and expect your types to play nicely with other stuff. If your stuff is wrapped in types that do define the proper functions for that (like in your example), then it can work, but the types which were wrapped won't play nice outside of the wrapper. This is true, but then my code is by definition not standard. However, theoretically, the language writers could. For example, any '==' could be lowered to a 'standard' function, probably better named 'intancesDeepEqual(a,b)' and that function could use reflection to provide equal when not available else call opEquals if it is available. Similar with opCmp, dup, idup, ... In other words, in the vein of the original poster, why not allow all of these nice goodies (equality comparison, opCmp comparison, dup) without requiring boilerplate code while still honoring/using it when it is provided. [...] I like this idea. By default, provide something that recursively compares struct/class members, array elements, etc.. But if at any level an opEquals is defined, then that is used instead. This maximizes convenience for those cases where you *do* just want a literal equality of all sub-structures, but also allows you to override that behaviour if your class/struct needs some other special processing. T -- How are you doing? Doing what?
Re: recursive equal, and firstDifference functions
On Tuesday, March 19, 2013 18:20:35 H. S. Teoh wrote: I like this idea. By default, provide something that recursively compares struct/class members, array elements, etc.. But if at any level an opEquals is defined, then that is used instead. This maximizes convenience for those cases where you *do* just want a literal equality of all sub-structures, but also allows you to override that behaviour if your class/struct needs some other special processing. We already get this. That's what == does by default. It's just that it uses == on each member, so if == doesn't work for a particular member variable and the semantics you want for == on the type it's in, you need to override opEquals. - Jonathan M Davis
Re: recursive equal, and firstDifference functions
On Wednesday, 20 March 2013 at 02:03:31 UTC, Jonathan M Davis
wrote:
We already get this. That's what == does by default. It's just
that it uses ==
on each member, so if == doesn't work for a particular member
variable and the
semantics you want for == on the type it's in, you need to
override opEquals.
Really?
string is one most people would like == to just work for. This
writes true then false. This certainly takes getting used to. It
alone is a good reason for the mixins and potentially a
non-member instancesDeepEqual.
import std.stdio;
struct S {
string s;
}
void main() {
writeln(foo == foo.idup);
writeln(S(foo) == S(foo.idup));
}
Re: recursive equal, and firstDifference functions
On Wednesday, March 20, 2013 03:48:38 Dan wrote:
On Wednesday, 20 March 2013 at 02:03:31 UTC, Jonathan M Davis
wrote:
We already get this. That's what == does by default. It's just
that it uses ==
on each member, so if == doesn't work for a particular member
variable and the
semantics you want for == on the type it's in, you need to
override opEquals.
Really?
string is one most people would like == to just work for. This
writes true then false. This certainly takes getting used to. It
alone is a good reason for the mixins and potentially a
non-member instancesDeepEqual.
import std.stdio;
struct S {
string s;
}
void main() {
writeln(foo == foo.idup);
writeln(S(foo) == S(foo.idup));
}
That's a bug:
http://d.puremagic.com/issues/show_bug.cgi?id=3789
- Jonathan M Davis
Re: recursive equal, and firstDifference functions
On Wednesday, March 20, 2013 01:17:13 Dan wrote: This is true, but then my code is by definition not standard. However, theoretically, the language writers could. For example, any '==' could be lowered to a 'standard' function, probably better named 'intancesDeepEqual(a,b)' and that function could use reflection to provide equal when not available else call opEquals if it is available. Similar with opCmp, dup, idup, ... In other words, in the vein of the original poster, why not allow all of these nice goodies (equality comparison, opCmp comparison, dup) without requiring boilerplate code while still honoring/using it when it is provided. Okay. I'm going to take a second stab at replying to this, because I think that I can explain it much better. The standard function that == lowers to is opEquals. Nothing else is needed. The way that == works is integral types, char types, pointers, and bool: bitwise comparison floating point types: equality which is similar to bitwise comparison but takes NaN into account arrays: The ptr and length attributes are checked, and if the lengths are equal but the ptrs are not, then element-wise comparison is used, where each element is compared with == (whereas if the lengths are different or if the ptr and length attributes are identical, no further comparison is needed). structs and classes: Their opEquals is used. If a struct or class does not define opEquals, then one is generated where each member variable is compared in turn with ==. So, they are compared recursively. They _only_ times that you need you need to worry about defining opEquals are when 1. the default comparison is comparing pointers, and you want to compare what they point to rather than the pointers themselves. 2. you want equality to mean something other than calling == on each member variable (including doing something other than == on a particular member variable as might be the case with a member variable which is a range). The way == is defined is very clean and straightforward. There _are_ bugs which complicate things (e.g. http://d.puremagic.com/issues/show_bug.cgi?id=3789 ), but those can and will be fixed. The design itself is solid. It's true that equal is often need for comparing ranges of the same type, but that's arguably a defect in the implementations of those ranges. equal is specifically designed to compare ranges which are different types but have the same element type. == is what's for comparing objects of the same type. But most ranges don't currently define opEquals, even when they need it in order for it to do a proper comparison. That's arguably something that should be fixed, but it's a design issue of ranges, not ==. But if you want to ensure that equal is used, you can always use a mixin to define opEquals that way (though you actually risk making the comparison less efficient than it would be if the ranges themselves defined opEquals). So, I can see a definite argument that ranges should make sure that they define opEquals (which wouldn't negate the general need for equal as that's specifically for comparing ranges of different types which have the same element type), but there's no need to change how == works. The design is actually very clean. - Jonathan M Davis
Re: recursive equal, and firstDifference functions
On Wednesday, 20 March 2013 at 02:54:23 UTC, Jonathan M Davis
wrote:
On Wednesday, March 20, 2013 03:48:38 Dan wrote:
On Wednesday, 20 March 2013 at 02:03:31 UTC, Jonathan M Davis
wrote:
We already get this. That's what == does by default. It's
just
that it uses ==
on each member, so if == doesn't work for a particular member
variable and the
semantics you want for == on the type it's in, you need to
override opEquals.
Really?
string is one most people would like == to just work for. This
writes true then false. This certainly takes getting used to.
It
alone is a good reason for the mixins and potentially a
non-member instancesDeepEqual.
import std.stdio;
struct S {
string s;
}
void main() {
writeln(foo == foo.idup);
writeln(S(foo) == S(foo.idup));
}
That's a bug:
http://d.puremagic.com/issues/show_bug.cgi?id=3789
From Feb 2010. Maybe by now it is so understood how it works that
at some point fixing it could be a problem. For some the language
is better defined by how the compiler treats your code than what
is listed in bugzilla. Even in looking through the history of
that bug I could not find any definitive - some say its a bug,
others say its not. You refer to TDPL which is a good source but
if it is not viewed as a bug by Walter...
