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.

Pluckless

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.

Telstar

What makes Const too magical? Yeah, the implementation of foldMapDefault is full of coercion magic, but that's not essential. – Fsh

@Fsh My judgment, based on this user's other questions, is that a good answer for this user should introduce one and only one new idea at a time. Turning a traversal into a fold is already that one idea. I can only hope that the writer monad was not a second idea already, let alone the less complicated but also less popular Const applicative. – Telstar

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.

Enchantress

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.

Kloster

There are definitely other reasons for superclasses. Num is a superclass of Integral because it doesn't make sense for something to be integral if it's not a number. Semigroup is (now) a superclass of Monoid because a monoid is a semigroup with an identity element (mathematically). – Fsh

@Fsh The semigroup-monoid relation arguably falls under point (2) here. – Telstar

@DanielWagner, that's purely a historical accident. – Fsh