Why does the Functor type class not include a fold method?

Question

Why does the type class Functor have only the memberfmap? I often find it useful to perform a fold over datatypes. Say, hierarchical ones, like a tree.

Note that a map is a special case of fold, that is, the latter is more fundamental. I guess I can take it the way it is, but maybe there is a reason?

Answer 1

Because a Functor is a very general kind of object; not all Functors support folds. For example, there is an instance¹

instance Functor (a ->) where
     -- > fmap :: (b -> c) -> (a -> b) -> (a -> c)
     fmap f g = g . f

But, while (a ->) is a Functor for all a, for infinite a there isn't a reasonable fold definition. (Incidentally, a 'fold' in general is a catamorphism, which means it has a different type for each functor. The Foldable type class defines it for sequence-like types.).

Consider what the foldr definition for Integer -> Integer would look like; what would the outermost application be? What would the value of

foldr (\ _ n -> 1 + n) 0 (\ n -> n + 1)

be? There isn't a reasonable definition of fold without a lot more structure on the argument type.

¹(a ->) isn't legal Haskell for some reason. But I'm going to use it anyway as a more readable version of (->) a, since I think it's easier for a novice to understand.

Answer 2

The abstraction you are looking for is Foldable: This is a type class providing variuos forms of fold.

There is also Traversable for things where you can “fold while changing”, comparable to the mapAccumL function for lists.

It is actually not true that fmap is a special case of fold, as pointed out by @DietrichEpp, see as here are possible non-Functor instances of Foldable.

map is however a special case of mapAccumL (no surprise, given the name), and hence the definition of Traversable requires the thing to be also a Functor and a Foldable.