3 ms·
How would you implement and test something something like C++'s unordered_set, a set with constant insert and lookup, using type-level constraints instead of un
by jpcooper 6y ago
How would you implement and test something something like C++'s unordered_set, a set with constant insert and lookup, using type-level constraints instead of unit tests? How would you represent this with types?
- dragonwriter 6y ago> How would you implement and test something something like C++'s unordered_set, a set with constant insert and lookup, using type-level constraints instead of unit tests? How do you test asymptotic behavior with unit tests? It would seem that is the kind of thing which is analytically demonstrable from the input types knowledge of the same features of the underlying operations (and, thus, theoretically within reach of a type system, if you wanted to design a type system with that in mind), but only subject to loose approximation in anything like unit testing.
- jpcooper 6y agoTesting asymptotic behaviour is quite simple. It can be done empirically. Yes, you might make a formal proof of asymptotic behaviour and the property that the iterator returns a set, given a certain approximate model of the system, of course. However, it doesn’t just become simple or practical given the existence of a suitable type system alone. Also I am not sure of the usefulness of tests of the asymptotic behaviour of an implementation of a data structure over tests over the applicable data and system. Is there a demand for this? What I mean is separate from the proof that a theoretical hash set had X complexity in its operations. That is clearly interesting. Unit testing might be for the poor man, but how much money will the man doing the formal proof have left at the end of it?