On Wed, Oct 24, 2012 at 09:41:41PM +0200, Mehrdad wrote:
> On Wednesday, 24 October 2012 at 19:34:15 UTC, H. S. Teoh wrote:
> >I don't know if there is any struct-specific problem here, but AA comparison right now is horribly horribly broken (search on the bug tracker for "AA" and you'll see a bunch of issues on that end). You're incredibly lucky that two AA literals actually compared equal. In some cases, not even that is guaranteed.
> 
> 
> Yeah, I was a little aware that AAs were semi-broken, but I thought,
> hey, if it seems to work then it obviously works.
> Turns out that wasn't so true. :\

The AA implementation badly needs to be revamped. But the problem is that it's non-trivial, may break existing code, etc.. I do have a (semi) working version of a prospective AA replacement, though:

	https://github.com/quickfur/New-AA-implementation

You might be able to make use of it if you're willing to live with broken IFTI (which is no big deal if you just explicitly type what you instantiate the AA with).


> >I've tried to clean up the AA code but it's a tangled messy ugly labyrinth with fragile hacks sprinkled in, and didn't get to the point where it's ready to commit. One major obstacle is that parts of it are implemented in compiler hacks, and part of it is schizophrenically duplicated in object_.d, not necessarily consistently, and it's just Not Nice in general. That it works at all is reason enough to be thankful. I don't expect things to be pretty once you start poking into the intricacies of AA's, sad to say.
> 
> Yeah, the trouble is, none of the set-based data types (including
> maps) in D seem to be working...
> 
> - AAs are broken
> - AssociativeArray is the same as above, I think?

Yes it's the same. It's not meant to be used directly by user code, though. The two are supposed to be the same.


> - RedBlackTree is useless (how do I keep a "set of sets"?)

What's wrong with RedBlackTree? You can just do something like:

	RedBlackTree!(RedBlackTree!MySet) setOfSets;


[...]
> So you can't really write a real program in D, to put it blunty.

That's a bit harsh. It's not hard to write your own hash implementation in D, given the expressiveness of its templates and compile-time features. The bugginess of the built-in AA is lamentable, definitely, but it doesn't *prevent* you from writing your own data structures. All programmers worth their salt should be able to roll their own where the current implementation is inadequate, anyway. ;-) In any case, as they say in the open source community, patches are always welcome.

Plus, you *can* use AA's for all sorts of stuff in general, if you just avoid some of the most glaring bugs. It only takes 15 minutes to write your own opEquals() in a struct that wraps around an AA, and it's equally fast to parametrize that struct to take arbitrary types, and provide wrapper functions that work around the current bugs. None of the current issues are showstoppers, as annoying as they may be.


T

-- 
Do not reason with the unreasonable; you lose by definition.

On 2012-10-24 21:37, Mehrdad wrote:

> I don't know what to expect code like this to do (unlike in C++, where
> everything is clearly defined in the specs), and when it seems to do
> what I want, it really turns out to be a bug in the library that it
> seemed to work in the first place. :(

Everything in C++ is specified as undefined behavior :)

-- 
/Jacob Carlborg

On Wed, Oct 24, 2012 at 09:50:18PM +0200, Mehrdad wrote:
> On Wednesday, 24 October 2012 at 19:41:42 UTC, Mehrdad wrote:
> >So you can't really write a real program in D, to put it bluntly.
> 
> 
> Case in point: there's no way to tell an arbitrary object/struct to give you its hash code.

Huh?  All objects implement toHash(). If the default toHash() doesn't
satisfy you, override it with your own.

You can just use rt.util.hash.hashOf for structs. Use UFCS to make it
callable as toHash(). Implement your own toHash() where hashOf isn't
good enough. Problem solved.


T

-- 
Once bitten, twice cry...

On Wednesday, 24 October 2012 at 20:04:24 UTC, Jacob Carlborg wrote:
> On 2012-10-24 21:37, Mehrdad wrote:
>
>> I don't know what to expect code like this to do (unlike in C++, where everything is clearly defined in the specs), and when it seems to do what I want, it really turns out to be a bug in the library that it seemed to work in the first place. :(
>
> Everything in C++ is specified as undefined behavior :)



lol.


I meant more like, it's clear in C++ which operations need to be implemented in order for an object to be hashable, for instance.

I can't figure out how hashing works in D at all.

On Wednesday, 24 October 2012 at 20:07:49 UTC, H. S. Teoh wrote:
> On Wed, Oct 24, 2012 at 09:50:18PM +0200, Mehrdad wrote:
>> On Wednesday, 24 October 2012 at 19:41:42 UTC, Mehrdad wrote:
>> >So you can't really write a real program in D, to put it bluntly.
>> 
>> 
>> Case in point: there's no way to tell an arbitrary object/struct to
>> give you its hash code.
>
> Huh?  All objects implement toHash().


Not Tuples, apparently. (I didn't mean Object, I mean "object" in
the general sense.)


> You can just use rt.util.hash.hashOf for structs.

Will try, thanks for the pointer.

On Wed, Oct 24, 2012 at 10:09:36PM +0200, Mehrdad wrote:
> On Wednesday, 24 October 2012 at 20:07:49 UTC, H. S. Teoh wrote:
> >On Wed, Oct 24, 2012 at 09:50:18PM +0200, Mehrdad wrote:
> >>On Wednesday, 24 October 2012 at 19:41:42 UTC, Mehrdad wrote:
> >>>So you can't really write a real program in D, to put it bluntly.
> >>
> >>
> >>Case in point: there's no way to tell an arbitrary object/struct to give you its hash code.
> >
> >Huh?  All objects implement toHash().
> 
> 
> Not Tuples, apparently. (I didn't mean Object, I mean "object" in
> the general sense.)

Well, Object implements toHash(). Other things don't, but with UFCS you
can endow them with toHash(). :)


> >You can just use rt.util.hash.hashOf for structs.
> 
> Will try, thanks for the pointer.

hashOf works for pretty much anything (it's just a byte-based algo). So it's not just structs, you can pass anything to it. Using UFCS to map toHash() to hashOf will give you toHash() for literally everything, which is apparently what you want (though I question the wisdom of wanting a hash value of *everything*, including objects representing network resources, the OS, etc., but hey, you can do it if you *really* want to).


T

-- 
It won't be covered in the book. The source code has to be useful for something, after all. -- Larry Wall

On Wednesday, 24 October 2012 at 20:03:44 UTC, H. S. Teoh wrote:
> What's wrong with RedBlackTree? You can just do something like:
>
> 	RedBlackTree!(RedBlackTree!MySet) setOfSets;


The last time I checked two RedBlackTrees for equality, they seemed to have reference semantics...


>
> [...]
>> So you can't really write a real program in D, to put it blunty.
>
> That's a bit harsh.

Sorry, just saying what I experienced :(

> It's not hard to write your own hash implementation in D

I beg to differ, see below

> given the expressiveness of its templates and compile-time features. The bugginess of the built-in AA is lamentable, definitely, but it doesn't *prevent* you from writing your own data structures.

It does. There's simply no mechanism to hash an arbitrary thing in D.

(hashOf, which Andrej just mentioned, is an internal thing, right? aka a hack, which I was not aware of)


> All programmers worth their salt should be able to roll their own where the current implementation is inadequate, anyway. ;-)


Well, there's different issues involved...

- Can I? Yes.
- Will I? No, it takes more time than it's worth

> In any case,  as they say in the open source community, patches are always welcome.

Yeah, it's just that I can't figure out even the basics of hashing in D (above), so I can't really patch something because then it'll turn out to be working in a different way than I expect.

> It only takes 15 minutes to write your own opEquals() in a struct that wraps around an AA

I've spent longer than that right now and still haven't been able to (but I haven't tried the hashOf hack yet).



Maybe you can fill in the blanks?


struct Set(T)
{
	int[T] dict;
	hash_t toHash() const
	{
		typeof(return) r = 0;
		foreach (item; this.dict.keys)
		{
			???       // what should be here?
		}
		return r;
	}
}

On Wednesday, 24 October 2012 at 20:15:07 UTC, H. S. Teoh wrote:
> hashOf works for pretty much anything (it's just a byte-based algo).


Byte-based?

what about


	Set!(Tuple!(int, string)) s;
	s[tuple(1, "hi")] = 1;
	writeln(tuple(1, "hi".dup) in s);  // null or not?

On Wednesday, 24 October 2012 at 20:18:07 UTC, Mehrdad wrote:
> On Wednesday, 24 October 2012 at 20:15:07 UTC, H. S. Teoh wrote:
>> hashOf works for pretty much anything (it's just a byte-based algo).
>
>
> Byte-based?
>
> what about
>
>
> 	Set!(Tuple!(int, string)) s;
> 	s[tuple(1, "hi")] = 1;
> 	writeln(tuple(1, "hi".dup) in s);  // null or not?

my bad, I mixed up AA and sets.

That was supposed to insert the item, not map it to 1. Would it work?

On 10/24/2012 12:17 PM, Mehrdad wrote:
> I couldn't find a better title, sorry.
>
>
> But yeah, I've spent too many hours on hunting down problems like these...
>
>
> Could someone explain what's going on? Thanks!
>
> import std.stdio;
> struct S { int[int] aa; }
> void main()
> {
>      writeln(  [1: 2]  ==   [1: 2] );  // true
>      writeln(S([1: 2]) == S([1: 2]));  // false
> }
>
> (I'm on Windows DMD v2.060.)

The compare for associative arrays is to compare the members.

The default compare for structs is a bit compare of the contents.