What would be the "distinct method" that Traversable has in addition to Foldable?

containers, fold, haskell, traversable

Solution

`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.

Problem

`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.

Original source