An example of a Foldable which is not a Functor (or not Traversable)?

A Foldable instance is likely to be some sort of container, and so is likely to be a Functor as well. Indeed, this says

A Foldable type is also a container (although the class does not technically require Functor, interesting Foldables are all Functors).

So is there an example of a Foldable which is not naturally a Functor or a Traversable? (which perhaps the Haskell wiki page missed :-) )

Solution 1:

Here's a fully parametric example:

data Weird a = Weird a (a -> a)

instance Foldable Weird where
  foldMap f (Weird a b) = f $ b a

Weird is not a Functor because a occurs in a negative position.

Solution 2:

Here's an easy example: Data.Set.Set. See for yourself.

The reason for this should be apparent if you examine the types of the specialized fold and map functions defined for Set:

foldr :: (a -> b -> b) -> b -> Set a -> b

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

Because the data structure relies on a binary search tree internally, an Ord constraint is needed for elements. Functor instances must allow any element type, so that's not viable, alas.

Folding, on the other hand, always destroys the tree to produce the summary value, so there's no need to sort the intermediate results of the fold. Even if the fold is actually building a new Set, the responsibility for satisfying the Ord constraint lies on the accumulation function passed to the fold, not the fold itself.

The same will probably apply to any container type that's not fully parametric. And given the utility of Data.Set, this makes the remark you quoted about "interesting" Foldables seem a bit suspect, I think!