Download Typeclassopedia - Tufts University Computer Science

2. traverse (Compose .
fmap g .
f) = Compose .
fmap (traverse g) .
traverse f
The first law essentially says that traversals cannot make up arbitrary effects. The second law explains how doing two
traversals in sequence can be collapsed to a single traversal.
Additionally, suppose eta is an "Applicative morphism", that is,
eta :: forall a f g. (Applicative f, Applicative g) => f a -> g a
and eta preserves the Applicative operations: eta (pure x) = pure x and eta (x <*> y) = eta x <*> eta y.
Then, by parametricity, any instance of Traversable satisfying the above two laws will also satisfy eta . traverse
f = traverse (eta . f).
Further reading
The Traversable class also had its genesis in McBride and Paterson’s Applicative paper, and is described in more
detail in Gibbons and Oliveira, The Essence of the Iterator Pattern, which also contains a wealth of references to
related work.
Traversable forms a core component of Edward Kmett’s lens library. Watching Edward’s talk on the subject is a
highly recommended way to gain better insight into Traversable, Foldable, Applicative, and many other things
besides.
For references on the Traversable laws, see Russell O’Connor’s mailing list post (and subsequent thread).
Category
Category is a relatively recent addition to the Haskell standard libraries. It generalizes the notion of function
composition to general “morphisms”.
The definition of the Category type class (from Control.Category; haddock) is shown below. For ease of reading,
note that I have used an infix type variable ‘arr‘, in parallel with the infix function type constructor (->). This
syntax is not part of Haskell 2010. The second definition shown is the one used in the standard libraries. For the
remainder of this document, I will use the infix type constructor ‘arr‘ for Category as well as Arrow.
class Category arr where
id :: a `arr` a
(.) :: (b `arr` c) -> (a `arr` b) -> (a `arr` c)
-- The same thing, with a normal (prefix) type constructor
class Category cat where
id :: cat a a
(.) :: cat b c -> cat a b -> cat a c
Note that an instance of Category should be a type constructor which takes two type arguments, that is, something of
kind * -> * -> *. It is instructive to imagine the type constructor variable cat replaced by the function constructor
(->): indeed, in this case we recover precisely the familiar identity function id and function composition operator
(.) defined in the standard Prelude.
Of course, the Category module provides exactly such an instance of Category for (->). But it also provides one
other instance, shown below, which should be familiar from the previous discussion of the Monad laws. Kleisli m a
b, as defined in the Control.Arrow module, is just a newtype wrapper around a -> m b.
newtype Kleisli m a b = Kleisli { runKleisli :: a -> m b }
instance Monad m => Category (Kleisli m) where
id = Kleisli return
Kleisli g . Kleisli h = Kleisli (h >=> g)
29