Time to add the Traversable laws to the Documentation

[roconnor at theorem.ca]

How about adding the following to the documentation of Traversable:

Any instance must statisfy the following three laws:

(0) eta . traverse f = traverse (eta . f)

     for every

     eta :: forall a f g. (Applicative f, Applicative g) => f a -> g a

     such that

     eta (pure x) = pure x

     and

     eta (x <*> y) = eta x <*> eta y

(1) traverse Identity = Identity

     where

     newtype Identity a = Identity a

     instance Functor Identity where
       fmap f (Identity x) = Identity (f x)

     instance Applicative Indentity where
       pure x = Identity x
       Identity f <*> Identity x = Identity (f x)

(2) traverse (Compose . fmap g . f) = Compose . fmap (traverse g) . traverse f

     where

     newtype Compose f g a = Compose (f (g a))

     instance (Functor f, Functor g) => Functor (Compose f g) where
       fmap f (Compose x) = Compose (fmap (fmap f) x)

     instance (Applicative f, Applicatve g) => Applicative (Compose f g) where
       pure x = Compose (pure (pure x))
       Compose f <*> Compose x = Compose ((<*>) <$> f <*> x)

Note: By parametricity, law (0) will hold uncondtionally and only laws (1) 
and (2) need be checked.

On Sat, 25 Aug 2012, roconnor at theorem.ca wrote:

> On Sat, 25 Aug 2012, Ross Paterson wrote:
>
>> On Fri, Aug 24, 2012 at 02:53:30AM +0100, roconnor at theorem.ca wrote:
>>> On Fri, 24 Aug 2012, Ross Paterson wrote:
>>> 
>>>> On Fri, Aug 24, 2012 at 12:08:04AM +0100, roconnor at theorem.ca wrote:
>>>>> With such wide spread agreement going back at least 6 years, I think it 
>>>>> is
>>>>> time to add the following 2 laws to the documentation for
>>>>> Data.Traversable.Traversable.
>>>>> 
>>>>> (1) traverse Identity == Identity
>>>>> (2) traverse (Compose . fmap g . f) == Compose . fmap (traverse g) . 
>>>>> traverse f
>>>> 
>>>> Sounds good (except that Identity and Compose aren't defined in base).
>>> 
>>> Er right.  I'm not entirely sure how to address this issue.
>> 
>> There doesn't seem to be any alternative to re-iterating the newtype
>> definitions and the Functor and Applicative instances in the doc comment.
>
> The only alternative I can think of would be to move the Idenity and Compose 
> functors from transformers into base.  The consequences of this would be 
> massive.  I don't really suggest doing this at this time.
>
>>> If you want to follow the terminology from "Essence of the Iterator
>>> Pattern" of using "idiomatic" for adjectives, you would call t an
>>> "Idiomatic transformation".
>> 
>> Noooo, please don't do that.  The transformations should match the
>> functors, and the adjective "applicative" at least has a grain of
>> relevant meaning.
>
> Okay.
>
>

-- 
Russell O'Connor                                      <http://r6.ca/>
``All talk about `theft,''' the general counsel of the American Graphophone
Company wrote, ``is the merest claptrap, for there exists no property in
ideas musical, literary or artistic, except as defined by statute.''