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 toFunctor
asTraversable
is toMonad
, i.e.Foldable
andFunctor
are superclasses ofMonad
andTraversable
(modulo all the applicative/monad proposal noise).Indeed, that's already in the code
So, it's not clear what more there is to want.
Foldable
is characterized bytoList :: Foldable f => f a -> [a]
whileTraversable
depends ultimately on not only being able to abstract the content as a list liketoList
does, but also to be able to extract the shapeand then recombine them
which depends on
traverse
.For more information on this property see this blog post by Russell O'Connor.