Functor instance for Set?

[Twan van Laarhoven]

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