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);
}

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.

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

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

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

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

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.

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);
}

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

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