Why are Foldable and Functor separate classes?

Question

The wiki page says both classes deal with container operations, with Foldable being a class of containers that have foldr defined over them, and for Functor it's fmap.

However, what is the fundamental difference between types that are Foldable and types that are Functors?

The wiki hints at this distinction:

The class [Foldable] does not require Functor superclass in order to allow containers like Set or StorableVector

But I'm still not sure why a Set couldn't be mapped over to obtain another set, if I'm interpreting that correctly.

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

The Functor typeclass doesn’t let you fmap over things that have constraints on the types of their elements. Set requires Ord and StorableVector requires Storable.

It is possible to express a “constrained functor” using GHC’s ConstraintKinds extension, something like:

{-# LANGUAGE ConstraintKinds,
             FunctionalDependencies,
             MultiParamTypeClasses #-}

import GHC.Exts (Constraint)
import Data.Set (Set)
import qualified Data.Set as Set

class ConstrainedFunctor c f | f -> c where
  cfmap :: (c a, c b) => (a -> b) -> f a -> f b

instance ConstrainedFunctor Ord Set where
  cfmap = Set.map

But this machinery wasn’t around when Functor first appeared.

In addition, Functor is supposed to be “shape-preserving”, but e.g. mapping over a Set may change its size.