Foldable is a superclass of Traversable, similarly to how Functor is a superclass of Applicative and Monad.
Similar to the case of Monad, where it is possible to basically implement fmap as
liftM :: Monad m => (a->b) -> m a -> m b
liftM f q = return . f =<< q
we could also emulate foldMap as
foldLiftT :: (Traversable t, Monoid m) => (a -> m) -> t a -> m
foldLiftT f = fst . traverse (f >>> \x -> (x,x))
-- or: . sequenceA . fmap (f >>> \x -> (x, x))
using the Monoid m => (,) m monad. So the combination of superclass and methods bears in both cases a certain redundancy.
In case of monads, it can be argued that a “better” definition of the type class would be (I'll skip applicative / monoidal)
class (Functor m) => Monad m where
return :: a -> m a
join :: m (m a) -> m a
at least that's what's used in category theory. This definition does, without using the Functor superclass, not permit liftM, so it is without this redundancy.
Is a similar transformation possible for the Traversable class?
To clarify: what I'm after is a re-definition, let's call it,
class (Functor t, Foldable t) => Traversable t where
skim :: ???
such that we could make the actual Traverse methods top-level functions
sequenceA :: (Traversable t, Applicative f) => t (f a) -> f (t a)
but it would not be possible to make generically
instance (Traversable t) => Foldable t where
foldMap = ... skim ...
data T
instance Traversable T where
skim = ...
I'm not asking because I need this for something particular; it's a conceptual question so as to better understand the difference between Foldable and Traversable. Again much like Monad vs Functor: while >>= is much more convenient than join for everyday Haskell programming (because you usually need precisely this combination of fmap and join), the latter makes it simpler to grasp what a monad is about.
Foldable is to Functor as Traversable is to Monad, i.e. Foldable and Functor are superclasses of Monad and Traversable (modulo all the applicative/monad proposal noise).
Indeed, that's already in the code
instance Foldable f => Traversable f where
...
So, it's not clear what more there is to want. Foldable is characterized by toList :: Foldable f => f a -> [a] while Traversable depends ultimately on not only being able to abstract the content as a list like toList does, but also to be able to extract the shape
shape :: Functor f => f a -> f ()
shape = fmap (const ())
and then recombine them
combine :: Traversable f => f () -> [a] -> Maybe (f a)
combine f_ = evalStateT (traverse pop f_) where
pop :: StateT [a] Maybe a
pop = do x <- get
case x of
[] = empty
(a:as) = set as >> return a
which depends on traverse.
For more information on this property see this blog post by Russell O'Connor.