The purpose of the Traversable typeclass

Question

Could someone please explain to me, what is the purpose of the typeclass Traversable?

The typeclass definition is:

class (Functor t, Foldable t) => Traversable (t :: * -> *) where

So Traversable is a Functor t and Foldable t.

The traverse function is a member of Traversable and has the following signature:

traverse :: Applicative f => (a -> f b) -> t a -> f (t b)

Why does the result have to be wrapped into an applicative? What is the sense of it?

I have the following example:

module ExercisesTraversable where

  import Test.QuickCheck (Arbitrary, arbitrary)
  import Test.QuickCheck.Checkers (quickBatch, eq, (=-=), EqProp)
  import Test.QuickCheck.Classes (traversable)

  type TI = []

  newtype IdentityT a = IdentityT a
    deriving (Eq, Ord, Show)

  instance Functor IdentityT where
    fmap f (IdentityT a) = IdentityT (f a)

  instance Foldable IdentityT where
    foldMap f (IdentityT a) = f a

  instance Traversable IdentityT where
    traverse f (IdentityT a) = IdentityT <$> f a

  instance Arbitrary a => Arbitrary (IdentityT a) where
    arbitrary = do
      a <- arbitrary
      return (IdentityT a)

  instance Eq a => EqProp (IdentityT a) where (=-=) = eq

  main = do
    let trigger = undefined :: TI (Int, Int, [Int])
    quickBatch (traversable trigger)  

Let's take a look at the traverse implementation:

traverse f (IdentityT a) = IdentityT <$> f a

The result type of the application f a has to be an applicative, why? Would a functor not be enough?

Answer 1

Identity is a bit of a poor example as it always contains exactly one value. You're right – in this case, a Functor f constraint would be sufficient. But clearly, most traversables aren't so structurally trivial.

What traverse does is: it “visits”, in some well-specified order, all elements in a container, performs some operation on them, and reconstructs the structure as it was. This is more powerful than either

• Functor t, which also allows you to visit/modify all elements and reconstructs the structure, but only completely independent of one another (thus allowing to choose an arbitrary order-of-computation, returning a thunk to the structure before any of the elements have been (lazily) mapped at all, etc.).

• Foldable t, which brings the elements in a linear order, but does not reconstruct the structure. Basically, Foldable is just the class of containers that can be demoted to a simple list, as witnessed by

  toList :: Foldable t => t a -> [a]
  

  ...or to a concatenation of any monoidal type, via

  foldMap :: (Foldable t, Monoid m) => (a -> m) -> t a -> m
  

  Here, the results of the operation on each element are combined through the monoid operation (or, in case the are no elements, the result is mempty).

In case of traverse, the Applicative f constraint basically lifts this monoid-combining to something in which you can also reconstruct the structure. The correspondence is

mempty      ::   m
pure mempty :: f m

and

(<>)        ::   m ->   m ->   m
liftA2 (<>) :: f m -> f m -> f m

...but in addition, because f is also a functor, you can wrap the local results in any data constructor and thus build not only a generic list-like thing but an arbitrary container, including one with the original structure.