Functor instance for Set?
Twan van Laarhoven
twanvl at gmail.com
Wed Feb 29 20:21:08 CET 2012
On 2012-02-29 19:54, Daniel Gorín wrote:
> 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.
More information about the Libraries