Traversable instance for ((,) o) ?

Conor McBride conor at strictlypositive.org
Wed Jan 4 00:30:26 CET 2012


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




More information about the Libraries mailing list