[jrockway]

you can't even make Set a functor in Haskell

Well sure, because map on a set is only defined over functions that return values that can be compared for equality, whereas the generic functor map is defined over all functions.

[eru]

Exactly. (However Data.Set is only defined for comparable values, i.e. the Ord typeclass, not Eq.)

[jrockway]

That is an efficiency hack to make it O(n log n) instead of O(n^2) rather than an intrinsic property of sets, functors, or Haskell :)

[eru]

Indeed. But Hindley-Milner [1] type systems have trouble expressing commutative stuff in general.

[1] I hope I got the names correct.