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)
eta :: forall a f g. (Applicative f, Applicative g) => f a -> g a
eta (pure x) = pure x
eta (x <*> y) = eta x <*> eta y
(1) traverse Identity = Identity
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
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
>>>>> time to add the following 2 laws to the documentation for
>>>>> (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.
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.''
More information about the Libraries