It needs C++ Concepts to get the equivalent of type-classes:
auto concept Ord<typename T> {
bool compare(T, T);
}
class compare {
HugeClass salt;
bool compare(SaltedInt x, SaltedInt y) const {
compare(hash(salt, x), hash(salt, y));
}
};
template <typename R>
requires RandomIterator(R), Ord(ValueType(R))
void sort :: (R x) {...}
The correct version of compare is chosen by concept overloading.
Keean.
On 8 January 2015 at 02:18, Keean Schupke <[email protected]> wrote:
> Hmm, can't you just make HugeClass static in SaltedInt?
>
> Keean.
>
>
>
>
>
> On 8 January 2015 at 02:02, Geoffrey Irving <[email protected]> wrote:
>
>> int already has an instance of Ord. SaltedOrd would be another one,
>> thus non-coherence.
>>
>> Geoffrey
>>
>> On Wed, Jan 7, 2015 at 5:59 PM, Keean Schupke <[email protected]> wrote:
>> > Okay, I see what you are getting at now. I don't really see any problem
>> with
>> > the first C++ solution... How would non-coherent instances help?
>> >
>> > On 8 January 2015 at 01:24, Geoffrey Irving <[email protected]> wrote:
>> >>
>> >> On Wed, Jan 7, 2015 at 5:16 PM, Keean Schupke <[email protected]>
>> wrote:
>> >> > I'm probably being slow, but I don't see that. With sortBy you pass
>> the
>> >> > comparison function explicitly. With a 'view' the comparison
>> function is
>> >> > passed implicitly (by they type). That is the only difference. A
>> view is
>> >> > simply type that overrides the comparator.
>> >> >
>> >> > Where is the extra memory etc coming from?
>> >>
>> >> For concreteness, here's what it looks like in C++:
>> >>
>> >> template <class RandomAccessIterator>
>> >> void sort (RandomAccessIterator first, RandomAccessIterator last);
>> >>
>> >> template <class RandomAccessIterator, class Compare>
>> >> void sort (RandomAccessIterator first, RandomAccessIterator last,
>> >> Compare comp);
>> >>
>> >> The first is sort, the second is sortBy. Say the comparison function
>> >> looks like
>> >>
>> >> class SaltedCompare {
>> >> HugeClass salt;
>> >> bool operator()(int x, int y) const { return hash(salt,x) <
>> >> hash(salt,y); }
>> >> }
>> >>
>> >> where the salt is (for some reason) huge. In C++, we pass a single
>> >> instance of SaltedCompare to the second version of sort, and the first
>> >> two arguments can point directly into a flat array of ints.
>> >>
>> >> Instead, you propose making a SaltedInt type. At best, this would
>> >> look something like
>> >>
>> >> class SaltedInt {
>> >> HugeClass* salt;
>> >> int x;
>> >> bool operator<(...) { ... }
>> >> }
>> >>
>> >> We either add another memory indirection or store a copy of HugeClass
>> >> in every entry. In either case, we need to copy the array.
>> >>
>> >> Apologies if what I'm describing is different from the views you had in
>> >> mind.
>> >>
>> >> Geoffrey
>> >> _______________________________________________
>> >> bitc-dev mailing list
>> >> [email protected]
>> >> http://www.coyotos.org/mailman/listinfo/bitc-dev
>> >
>> >
>> >
>> > _______________________________________________
>> > bitc-dev mailing list
>> > [email protected]
>> > http://www.coyotos.org/mailman/listinfo/bitc-dev
>> >
>> _______________________________________________
>> bitc-dev mailing list
>> [email protected]
>> http://www.coyotos.org/mailman/listinfo/bitc-dev
>>
>
>
_______________________________________________
bitc-dev mailing list
[email protected]
http://www.coyotos.org/mailman/listinfo/bitc-dev
