On Friday, 4 December 2015 at 10:35:33 UTC, ZombineDev wrote:
However, here we're talking about API for containers and algorithms and I think that putting the complexity in the function signature is better than only using abstract data structures, because it makes you more aware of the consequences of your choice of data structures and algorithms that you make. If we can figure out a way to put even more information it may be even better.
Well, if the algorithm can choose between containers it might be interesting to query the characteristics of a set of operations on each container. Not sure if the method name is is the best way to do it. Although I guess having a generic find(x) and find_instantly(x) would be ok, if the latter verison basically means less than 200 cycles in all cases. If it means less than 2000 cycles I think it is not so useful.
Maybe it is possible to make the inference as static analysis and in addition make it possible for libraries to express various guarantees. Since it is worst case it would be acceptable that if analysis fails it will result in "unbounded".
