On 2012-02-29 19:54, Daniel Gorín wrote:
Hi
...
It appears to me, then, that if "Set a" were implemented as the sum of a list of a and a BST, it could be made an instance of Functor, Applicative and even Monad without affecting asymptotic complexity (proof of concept below). Am I right here? Would the overhead be significant? The one downside I can think of is that one would have to sacrifice the Foldable instance.
A problem is that you lose complexity guarantees. Consider for example: let ints = [0..1000000] let setA = Set.fromList ints let setB = fmap id setA let slow = all (`Set.member` setB) ints Each call to Set.member in slow will take O(n) instead of the expected O(log n), which means that this code takes O(n^2) instead of O(n*log n). The problem is that you keep converting the same set from a list to a tree over and over again. Twan