Why are Foldable and Functor separate classes?

Set and StorableVector are functors, you can indeed map functions over them.

But not any kind of function. For instance, you can't map (+) over a StorableArray of numbers: this would give an array of functions, and these are not storable.

So, these functors are not (endo-)functors on all of Hask, but only on a subcategory including the types of a particular class. This can't be expressed in Haskell98, in fact it has only become possible quite recently with the advent of constraint kinds. See this example:

instance Functor Set Ranking Ranking where
  fmap = constrainedFmap Set.map

Actually, sets also form a monad in Hask if you use some clever GADT tricks. But this isn't possible for all Foldable containers, hence the standard library doesn't require Functor f => Foldable f.

Suppose I have xs :: Set Int and I want to map the function putStrLn over it. This will be a problem because IO () doesn't have an Ord instance, so there's no way to figure out how to insert those actions into the result set. The type of fmap leaves no room for constraints on the type argument to the Functor.

IO also provides an example of something that's a Functor but that there isn't any meaningful way to foldMap.

It's worth mentioning that Foldable and Functor come together in the Traversable class, which gives substantially more power than either.

Foldable and Functor offer two separate abstractions for types with structures that can be folded (or reduced) and mapped over, respectively.

A Foldable holds values that can be enumerated and combined together¹. One can think of a Foldable as something that can be turned into a list (toList :: Foldable f => f a -> [a]). Alternatively, one can think of Foldables as structures whose values can be combined monoidally: (Foldable t, Monoid m) => (a -> m) -> t a -> m (of course, this requires the ability to enumerate them).

Functors, on the other hand, are structures that allow one to "lift" a function (a -> b) to apply to the as held by the structure (fmap :: (a -> b) -> (f a -> f b)). fmap must preserve the structure being mapped over: a tree must have the same shape before and after, a list must have the same number of elements in the same order, Nothing can't be turned into something, and so on. On the other hand, Foldables do not need to preserve this structure; the whole point is to discard the structure and produce a new one.

The Wiki refers to the fact that there is no way to supply a typeclass constraint to fmap. fmap :: (Ord a, Ord b) => (a -> b) -> Set a -> Set b does not unify with the type defined by the class, fmap :: (a -> b) -> f a -> f b, which has no constraints. This makes an instance for Set impossible to write.

However, this is just a language implementation issue and not a deeper mathematic statement about sets. The real reason that Foldable does not have a Functor superclass is simply that there are Foldable instances which are not Functor instances.

---

1. "Hold" is a bit loose and is intended to be interpreted in the "Functors are containers" sense where Proxy s a holds zero a's, Identity a holds one a, Maybe a holds zero or one a, b -> a holds |b| a's, and so on.