How does Traversable use the fact that it subclasses both Foldable and Functor?

Question

class (Functor t, Foldable t) => Traversable t where

    traverse :: Applicative f => (a -> f b) -> t a -> f (t b)
    traverse g = sequenceA . fmap g

    sequenceA :: Applicative f => t (f a) -> f (t a)
    sequenceA = traverse id

How does Traversable use the fact that it subclasses both Foldable and Functor?

t being a traversable type implies t is also a functor type and a foldable type.

I see that the fact that t is a functor type, i.e. fmap , is used in traverse.

Is the fact that t is a foldable type used somewhere?

Does traverse use the fact that t is a foldable type?

Which fact does sequenceA use: t being a functor type, t being a foldable type, or both?

Can we define a class which is a subclass of Functor only and has both traverse and sequenceA functions defined in the same way?

Thanks.

Answer 1

The Foldable instance is not used. Nevertheless, it is fine to demand Foldable, since if we can traverse a thing, then we can foldMap it:

foldMapDefault :: (Traversable t, Monoid m) => (a -> m) -> t a -> m
foldMapDefault f = fst . traverse (\a -> (f a, ()))

The basic idea here is to use the standard writer monad; since the bind operation for the writer uses mappend to combine the "written" part -- here, the f a values -- traverse will mappend together just the right things. (It will also build up a t () that we don't actually care about; throwing away that part is the job of fst.)

For simplicity and self-containment, I've used the writer monad, but the true implementation uses the slightly mind-bending Const applicative to avoid building (and then throwing away) the uninteresting t () value. You may see the documentation of foldMapDefault here and its implementation here.

Answer 2

There are two main reasons for subclassing in general:

1. You need the class to make your definition work, or at least it makes the implementation so much more clear that it doesn't really make sense to leave it out. This is the case here for Functor.

2. You can derive the other class for free from the parts you already have for your main definition, so you may as well declare it. This is the case here for Foldable.