Foldable vs Traversable

Question

While studying Applicative deeper, I came to Traversable. Although I already knew Foldable from LYHGG, I haven't seen the former yet, so I started reading the Haskell wiki about Traversable.

While reading it, I understood why Foldable.fold is parallel to Traversable.sequenceA and Foldable.foldMap is parallel to Traversable.traverse.

I've seen also that every Traversable is also a Foldable and a Functor, and sequenceA and traversal have a default implementation in terms of each other:

traverse f = sequenceA . fmap f
sequenceA = traverse id

So, as I have seen in LYHGG that foldMap is a minimal complete definition for Foldable, I thought that, it is parallel to traverse, so fold (which is parallel to sequenceA) would be a minimal complete definition too (which it isn't)... Foldable is not a Functor like Traversable is, so we cannot apply this:

foldMap f = fold . fmap f
fold = foldMap id -- this is ok

Why isn't every Foldable a Functor, and what would be an instance of Foldable that actually isn't a Functor?

Answer 1

As dfeuer says, Set is a good example of a Foldable that isn't a Functor.

Consider the type of Set.map:

map :: Ord b => (a -> b) -> Set a -> Set b

Notice that this is almost fmap, but it requires an additional Ord b constraint. Since you have this constraint, it can't be made an instance of Functor.

Note that Set is not a functor on Haskell, even with this restriction. Given cleverly set-up Eq instances we can break the law that fmap f . fmap g === fmap (f . g). See this Stack Overflow question for further discussion.

As noted there, Set is an (endo) functor on the "subcategory of Hask" with ordered types as sets and with order-preserving maps as morphisms.

So even if it isn't apparent, the fact that we can't make Set a functor actually hints at a genuine mathematical issue and not just a limitation of our typeclass machinery.