Edward Kmett | 28 Jul 02:27 2012
Picon

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

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.

Discussion Period: 2 Weeks

-Edward Kmett

On Tue, Jan 3, 2012 at 7:50 PM, Ben Millwood <haskell <at> benmachine.co.uk> wrote:
Yeah, I noticed this the other day, and a couple of other instances
which aren't defined, but could be:

http://hpaste.org/56005

I won't pretend I have much use for the Const instance, but it seems
like it should be there anyway, just for completeness (I think it's
possible to define Traversable instances for compositions of functors,
possibly sums and products as well, so Const could be useful in that
context). I think the Either one makes sense, though, as a natural
analogue of the Maybe instance.

On Tue, Jan 3, 2012 at 11:41 PM, Conal Elliott <conal <at> conal.net> wrote:
> Thanks much for the answers, Conor. They all make sense to me, particularly
> about the typical information discarding in Foldable.
>
> Regards, - Conal
>
>
> On Tue, Jan 3, 2012 at 3:30 PM, Conor McBride <conor <at> strictlypositive.org>
> wrote:
>>
>>
>> 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
>>
>
>
> _______________________________________________
> 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

_______________________________________________
Libraries mailing list
Libraries <at> haskell.org
http://www.haskell.org/mailman/listinfo/libraries
Ross Paterson | 28 Jul 03:06 2012
Picon

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

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.
Edward Kmett | 28 Jul 03:58 2012
Picon

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

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


-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
Conor McBride | 28 Jul 10:59 2012

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

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
wren ng thornton | 30 Jul 05:27 2012

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

On 7/28/12 4:59 AM, Conor McBride wrote:
> 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.

Indeed. Though it's worth noting that in unification-fd[1] I recently 
switched from that exact type to the more powerful:

     class Traversable f => Unifiable f where
         zipMatch :: f a -> f a -> Maybe (f (Either a (a, a)))

The benefit of this latter type is that it allows the instance to 
declare success for unification sub-problems--- which is necessary for 
things like unification of feature-structures. The downside is that, 
since you only get one type for the solved subproblems, you lose the 
ability to distinguish the type variables a and b (not that it matters 
for unification).

[1] 
http://hackage.haskell.org/packages/archive/unification-fd/0.8.0/doc/html/Control-Unification-Types.html

--

-- 
Live well,
~wren

Gmane