base-4.14.0.0: Basic libraries
Copyright Conor McBride and Ross Paterson 2005 BSD-style (see the LICENSE file in the distribution) libraries@haskell.org experimental portable Trustworthy Haskell2010

Data.Traversable

Description

Class of data structures that can be traversed from left to right, performing an action on each element.

Synopsis

# The Traversable class

class (Functor t, Foldable t) => Traversable t where Source #

Functors representing data structures that can be traversed from left to right.

A definition of traverse must satisfy the following laws:

Naturality
t . traverse f = traverse (t . f) for every applicative transformation t
Identity
traverse Identity = Identity
Composition
traverse (Compose . fmap g . f) = Compose . fmap (traverse g) . traverse f

A definition of sequenceA must satisfy the following laws:

Naturality
t . sequenceA = sequenceA . fmap t for every applicative transformation t
Identity
sequenceA . fmap Identity = Identity
Composition
sequenceA . fmap Compose = Compose . fmap sequenceA . sequenceA

where an applicative transformation is a function

t :: (Applicative f, Applicative g) => f a -> g a

preserving the Applicative operations, i.e.

t (pure x) = pure x
t (f <*> x) = t f <*> t x


and the identity functor Identity and composition functors Compose are from Data.Functor.Identity and Data.Functor.Compose.

A result of the naturality law is a purity law for traverse

traverse pure = pure

(The naturality law is implied by parametricity and thus so is the purity law [1, p15].)

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:

• In the Functor instance, fmap should be equivalent to traversal with the identity applicative functor (fmapDefault).
• In the Foldable instance, foldMap should be equivalent to traversal with a constant applicative functor (foldMapDefault).

References: [1] The Essence of the Iterator Pattern, Jeremy Gibbons and Bruno C. d. S. Oliveira

Minimal complete definition

Methods

traverse :: Applicative f => (a -> f b) -> t a -> f (t b) Source #

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 traverse_.

sequenceA :: Applicative f => t (f a) -> f (t a) Source #

Evaluate each action in the structure from left to right, and collect the results. For a version that ignores the results see sequenceA_.

mapM :: Monad m => (a -> m b) -> t a -> m (t b) Source #

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 mapM_.

sequence :: Monad m => t (m a) -> m (t a) Source #

Evaluate each monadic action in the structure from left to right, and collect the results. For a version that ignores the results see sequence_.

#### Instances

Instances details

# Utility functions

for :: (Traversable t, Applicative f) => t a -> (a -> f b) -> f (t b) Source #

for is traverse with its arguments flipped. For a version that ignores the results see for_.

forM :: (Traversable t, Monad m) => t a -> (a -> m b) -> m (t b) Source #

forM is mapM with its arguments flipped. For a version that ignores the results see forM_.

mapAccumL :: Traversable t => (a -> b -> (a, c)) -> a -> t b -> (a, t c) Source #

The mapAccumL function behaves like a combination of fmap and 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 :: Traversable t => (a -> b -> (a, c)) -> a -> t b -> (a, t c) Source #

The mapAccumR function behaves like a combination of fmap and 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.

# General definitions for superclass methods

fmapDefault :: forall t a b. Traversable t => (a -> b) -> t a -> t b Source #

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.)

fmapDefault f ≡ runIdentity . traverse (Identity . f)


foldMapDefault :: forall t m a. (Traversable t, Monoid m) => (a -> m) -> t a -> m Source #

This function may be used as a value for foldMap in a Foldable instance.

foldMapDefault f ≡ getConst . traverse (Const . f)