# Time to add the Traversable laws to the Documentation

roconnor at theorem.ca roconnor at theorem.ca
Mon Oct 29 05:08:41 CET 2012

```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.''

```