Proposal: Add the missing instances for Traversable (Either b) and Traversable ((, ) b)

[Conor McBride]

Edward and comrades,

On 28 Jul 2012, at 02:58, Edward Kmett wrote:

> Fair enough. I'll try to switch my development environment around to something new enough that I can assemble a patch.

Any chance of throwing in the trivial instances for Const? (And
how about composition?)

Or maybe they can wait for a more coherent presentation of the
"Polynomial Functor Kit" (Const, Identity, closure under sum and
product).

It's a bit of a tangent, but the context I have in mind is that
all the polynomials are Foldable, Traversable and (the much
neglected) HalfZippable (the idea and the name I learned from
Roland Backhouse).

  class Functor f => HalfZippable f where
    halfZip :: f a -> f b -> Maybe (f (a, b))

which is a zip that can abort in case of shape mismatch. If a
functor is both Foldable and HalfZippable, then its (least)
fixpoint has a decidable equality (you try to zip each node
together, and if you succeed, you foldMap the equality test over
the paired children), and moreover, its free monad (chucking in
a representation of "free variables") has a unification
algorithm.

The Const instances may seem useless in isolation, but as part
of the kit, they're vital (allowing us to add labels to tree
structures).

A HalfZippable proposal might show up in a bit, but it would be
good to sort out the rest of the Foldable/Traversable components.

Cheers

Conor



> 
> -Edward
> 
> On Fri, Jul 27, 2012 at 9:06 PM, Ross Paterson <ross at soi.city.ac.uk> wrote:
> On Sat, Jul 28, 2012 at 01:27:47AM +0100, Edward Kmett wrote:
> > The following instances are missing and have only one sensible
> > definition. I've been bitten by their lack repeatedly and there is
> > no place outside of base that they can live without needlessly being
> > orphaned. 
> >
> > I would like to propose adding the following instances to Data.Foldable
> > and Data.Traversable.
> >
> > instance Foldable (Either e) where
> >    foldMap f (Right m) = f m
> >    foldMap _ (Left _) = mempty
> > instance Traversable (Either e) where
> >    traverse _ (Left e) = pure (Left e)
> >    traverse f (Right x) = Right <$> f x
> > instance Foldable ((,) e) where
> >    foldMap f (_,x) = f x
> > instance Traversable ((,) e) where
> >    traverse f (e,x) = (,) e <$> f x
> >
> > I had thought honestly thought we'd already added them long ago.
> 
> You proposed them in January 2011 and everyone agreed (after changing the
> pair instance to the strict versions given here) but I don't think you
> sent a patch to Ian.
> 
> http://thread.gmane.org/gmane.comp.lang.haskell.libraries/15196
> 
> It's certainly overdue.
> 
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://www.haskell.org/mailman/listinfo/libraries
> 
> _______________________________________________
> Libraries mailing list
> Libraries at haskell.org
> http://www.haskell.org/mailman/listinfo/libraries