Indexing with an arbitrary type

[Alex via Digitalmars-d-learn]

On Friday, 5 August 2016 at 16:37:14 UTC, Jonathan M Davis wrote:
> On Thursday, August 04, 2016 08:13:59 Alex via 
> Digitalmars-d-learn wrote:
>> What I think about is something like this: 
>> https://dpaste.dzfl.pl/d37cfb8e513d
>
> Okay, you have
>
> enum bool isKey(T) = is(typeof(T.init < T.init) : bool);
> template isNullable(T) { enum isNullable = __traits(compiles, 
> T.init.isNull);
> }
>
> struct IndexAble
> {
>     int[] arr;
>     this(size_t size)
>     {
>         arr.length = size;
>     }
>
>     ref int opIndex(T)(T ind) if(isKey!T)
>     {
>         static if(isNullable!T)
>             if(ind.isNull) return arr[$]; // or another 
> manually defined state.
>
>         return arr[ind];
>     }
> }
>
> What happens if I do this?
>
> void main()
> {
>     IndexAble indexable;
>     indexable["hello"];
> }
>
> You get a compilation error like
>
> q.d(17): Error: cannot implicitly convert expression (ind) of 
> type string to
> ulong
> q.d(24): Error: template instance q.IndexAble.opIndex!string 
> error
> instantiating
>
> because the index type of int[] is size_t, so it's only going 
> to accept values that are implicitly convertible to size_t, and 
> string is not implicitly convertible to size_t.

Yes. You are surely right.

> opIndex's template constraint did not catch the fact that 
> passing "hello" to opIndex would result in a compilation error. 
> string is perfectly comparable, and it's not a valid index type 
> for int[] - and comparability is all that opIndex's template 
> constraint checks for.

Right. My intension was to find the one check, which has to be 
fulfilled by all types, which could be used as an index...

>
> For opIndex to actually catch that an argument is not going to 
> compile if opIndex is instantiated with that type, then its 
> template constraint needs to either test that the index type 
> will implicitly convert to size_t so that it can be used to 
> index the int[],

Which would be too restrictive, as we have associative arrays...

> or it needs to test that indexing int[] with the argument will 
> compile. So, something like

I see the technical point, but the question which I want to 
answer with the isKey template is a different one. Maybe, a 
better formulation would be: "is a type uniquely convertible to 
size_t".

>
> ref int opIndex(T)(T ind)
>     if(is(T : size_t))
> {...}
>
> or
>
> ref int opIndex(T)(T ind)
>     if(__traits(compiles, arr[ind]))
> {...}
>
> And given that you're dealing explicitly with int[] and not an 
> arbitrary type, it really makes more sense to use is(T : 
> size_t). If IndexAble were templated on the type for arr, then 
> you would need to do the second. But testing for comparability 
> is completely insufficient for testing whether the type can be 
> used as an index.

I think, if I separate the concern of "can use sth. as key" and 
"how to use sth. as key" the isKey template is sufficient for the 
first one. Sure, without providing the answer for what...

> In fact, it's pretty much irrelevant. What matters is whether 
> the index type will compile with the code that it's being used 
> in inside the template. If you're forwarding the index variable 
> to another object's opIndex, then what matters is whether that 
> opIndex will compile with the index, and if you're doing 
> something else with it, then what matters is that it compiles 
> with whatever it is that you're doing with it.

Right. I just wanted to clarify for myself, what is the minimum 
requirement for a "key" is. Meanwhile, I'm close to the view, 
that it has to provide some conversion to size_t, providing 
toHash is maybe nothing else...

> I could declare a hash map implementation which did not use 
> opCmp but just used opEquals and toHash. Then I could have a 
> struct like
>
> struct S
> {
>     int i;
>     int j;
>
>     size_t toHash()
>     {
>         return i * j % size_t.max;
>     }
> }
>
> It has an opEquals (the implicit one declared by the compiler). 
> It has a toHash. It does not have opCmp (and the compiler won't 
> generate one). So, it's not comparable. But it would work in my 
> hash map type only used toHash and opEquals and not opCmp.
>
> HashMap!(S, string) hm;
> hm[S(5, 22)] = "hello world";
>
> And actually, while D's built-in AA's used to use opCmp (and 
> thus required it), they don't anymore. So, that code even works 
> with the built-in AA's. e.g.
>
> string[S] aa;
> aa[S(5, 22)] = "hello world";
>

Yeah. But you have either a perfect hashing and the absence of 
opCmp is the point what I'm wondering about. Or, the hashing is 
not perfect and then the usage of a key type relies on handling 
of collisions.

> So, comparability has nothing to do with whether a particular 
> type will work as the key for an indexable type. What matters 
> is that the index operator be given an argument that will 
> compile with it - which usually means a type which is 
> implicitly convertible to the type that it uses for its indices 
> but in more complex implementations where opIndex might accept 
> a variety of types for whatever reason, then what matters is 
> whether the type that you want to pass it will compile with it.

At the end - yes, I totally agree :)

> And unless all that that particular opIndex implentation needs 
> to care about for a type to work with it is that the type is 
> comparable, then testing that the type that you're going to 
> give it is comparable is insufficient and may not even be 
> relevant.

Ok, the relevance is a good point... And yes... you are probably 
right.
As a complement: I surely can't define an opIndex operator on all 
types, which come through my isKey template. Nor, the template 
can check, if a type can be used as an index for something. Even 
if I make a templated opIndex, I would not know, how to handle 
all value, which comes as an input.

I think, what the template is good for is to check, if it is 
possible to define an opIndex in the terms of a type at all, and 
providing a hash method is just a workaround for not providing a 
strict comparison.