Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Can the Traversable laws be derived from the fact that every Traversable is also a Functor?

I've been thinking why does the Traversable type class require both a Functor and Foldable, and not just the Foldable, since it doesn't use any part of the Functor?

class (Functor t, Foldable t) => Traversable t where
    traverse  :: Applicative f => (a -> f b) -> t a -> f (t b)
    sequenceA :: Applicative f => t (f a) -> f (t a)

Is seems that the laws for Traversable were not present in the documentation for base 4.6, which makes me think that they could be derived from the fact that every Traversable is a Functor?

In the Essence of the Iterator Pattern paper (section 5.1) it states that there are some free theorems for traverse which come directly from its type, but the paper doesn't go into depth describing why this is the case.

Where do the Traversable laws as described in the base 4.7 documentation come from?

like image 579
Jakub Arnold Avatar asked Jul 30 '14 12:07

Jakub Arnold


1 Answers

Basically, any type constructor * -> * that's covariant in its argument is canonically a functor. Since Applicative f is obviously covariant, so is t for the signature sequenceA :: t (f a) -> f (t a) to make sense, hence the Functor requirement is essentially redundant. But much like with the long-missing-because-unneeded Applicative => Monad superclass, it's not really a good idea to omit such "obvious" requirements, it just leads to code duplication and confusing synonymous functions.

like image 171
leftaroundabout Avatar answered Oct 21 '22 01:10

leftaroundabout