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

From here, class Traversable is a Functor and a Foldable, and must satisfy the laws:

And Foldable see more here. That means that it can be folded (foldMap, foldr, foldl...)

traverse function must satisfy the laws:

• naturality:

  t . traverse f = traverse (t . f) for every applicative transformation t

• identity

  traverse Identity = Identity

• composition

  traverse (Compose . fmap g . f) = Compose . fmap (traverse g) . traverse f

and sequenceA:

• naturality

  t . sequenceA = sequenceA . fmap t for every applicative transformation t

• identity

  sequenceA . fmap Identity = Identity

• composition

  sequenceA . fmap Compose = Compose . fmap sequenceA . sequenceA

Which fact does sequenceA use: t being a Functor type, t being a Foldable type, or both?

Traversable, as its definition says (and the laws quoted above):

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

is both, a Functor and a Foldable, by the laws it has to obey, it is not only a Functor, is more specific than a Functor (but still a Functor because satisfies the laws of Functor and can use the functions of its typeclass interface), and even more specific than Foldable, hence powerful, less general, with more constraints.

And what's the fact? The definition, but why the designer of Traversable choose those two? Because is useful, as you can see in @Daniel Wagner answer. Other examples:

instance Traversable [] where
    traverse f = List.foldr cons_f (pure [])
      where cons_f x ys = liftA2 (:) (f x) ys

this one uses foldr

instance Foldable [] where
    elem    = List.elem
    foldl   = List.foldl
    foldl'  = List.foldl'
    foldl1  = List.foldl1
    foldr   = List.foldr
    foldr1  = List.foldr1
    length  = List.length
    maximum = List.maximum
    minimum = List.minimum
    null    = List.null
    product = List.product
    sum     = List.sum
    toList  = id

So, Traverse is a Functor and a Foldable so you could use the functions of its interface when needed. (as in the example, is just an example not a justification of why the designer chooses to define Traversable with Functor and Foldable), is because is useful.

Answer 3

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.