Traversable instance for ((,) o) ?

[Conor McBride]

On 3 Jan 2012, at 23:12, Conal Elliott wrote:

> I wanted a Traversable instance for pairing, so I defined one:
> > instance Traversable ((,) o) where
> >   sequenceA (o,fa) = (o,) <$> fa

That looks right. Of course, we should really have a BiTraversable
class of which (,) is an instance.

>
> However, Foldable is a superclass of Traversable, so I get an error  
> message:
>
>     Could not deduce (Foldable ((,) o)) from the context ()
>       arising from the superclasses of an instance declaration
>
> The best I've thought of is the following:
>
> > instance Foldable ((,) o) where
> >   fold (_,m) = m

The best (upto efficiency considerations) is always

   instance Foldable ((,) o) where
     foldMap = foldMapDefault

which amounts to what you chose.

SHE makes this a default superclass instance.

> However, I don't like how it discards information.

But these folds always do discard information, discarding the shape
information and accumulating over the contents. For ((,) o), seen as
a functor, the first component is shape information and the second is
the content.

> Some questions:
>
> * Why is Foldable a superclass of Traversable?

Because the constant-monoid Applicative makes every Traversable
Foldable in a uniform way.

> * Is there a good choice of a Foldable instance of ((,) o)?

Yes, the one you chose.

> * Are there any other problems with the Traversable instance above  
> (besides foldability)?

Nope. It's the Traversable instance which picks out exactly the
contents that correspond to the elements abstracted by the Functor.

All the best

Conor