|Copyright||Conor McBride and Ross Paterson 2005|
|License||BSD-style (see the LICENSE file in the distribution)|
Class of data structures that can be traversed from left to right, performing an action on each element.
Functors representing data structures that can be traversed from left to right.
A definition of
traverse must satisfy the following laws:
t . traverse f = traverse (t . f)for every applicative transformation
traverse Identity = Identity
traverse (Compose . fmap g . f) = Compose . fmap (traverse g) . traverse f
A definition of
sequenceA must satisfy the following laws:
t . sequenceA = sequenceA . fmap tfor every applicative transformation
sequenceA . fmap Identity = Identity
sequenceA . fmap Compose = Compose . fmap sequenceA . sequenceA
where an applicative transformation is a function
t :: (Applicative f, Applicative g) => f a -> g a
Applicative operations, i.e.
and the identity functor
Identity and composition of functors
Compose are defined as
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) 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, Applicative g) => Applicative (Compose f g) where pure x = Compose (pure (pure x)) Compose f <*> Compose x = Compose ((<*>) <$> f <*> x)
(The naturality law is implied by parametricity.)
Instances are similar to
Functor, e.g. given a data type
data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)
a suitable instance would be
instance Traversable Tree where traverse f Empty = pure Empty traverse f (Leaf x) = Leaf <$> f x traverse f (Node l k r) = Node <$> traverse f l <*> f k <*> traverse f r
This is suitable even for abstract types, as the laws for
<*> imply a form of associativity.
The superclass instances should satisfy the following:
fmapshould be equivalent to traversal with the identity applicative functor (
foldMapshould be equivalent to traversal with a constant applicative functor (
Map each element of a structure to an action, evaluate these actions from left to right, and collect the results. For a version that ignores the results see
Evaluate each action in the structure from left to right, and and collect the results. For a version that ignores the results see
Map each element of a structure to a monadic action, evaluate these actions from left to right, and collect the results. For a version that ignores the results see
Evaluate each monadic action in the structure from left to right, and collect the results. For a version that ignores the results see
mapAccumL function behaves like a combination of
foldl; it applies a function to each element of a structure, passing an accumulating parameter from left to right, and returning a final value of this accumulator together with the new structure.
mapAccumR function behaves like a combination of
foldr; it applies a function to each element of a structure, passing an accumulating parameter from right to left, and returning a final value of this accumulator together with the new structure.
This function may be used as a value for
fmap in a
Functor instance, provided that
traverse is defined. (Using
fmapDefault with a
Traversable instance defined only by
sequenceA will result in infinite recursion.)
© The University of Glasgow and others
Licensed under a BSD-style license (see top of the page).