Proposal: Add the missing instances for Traversable (Either b) and Traversable ((, ) b)
Conor McBride
conor at strictlypositive.org
Sat Jul 28 10:59:16 CEST 2012
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
More information about the Libraries
mailing list