base-4.7.0.0: Basic libraries

CopyrightConor McBride and Ross Paterson 2005
LicenseConor McBride and Ross Paterson 2005
Maintainerlibraries@haskell.org
Stabilityexperimental
Portabilityportable
Safe HaskellTrustworthy

Data.Traversable

Contents

Description

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

See also

Note that the functions mapM and sequence generalize Prelude functions of the same names from lists to any Traversable functor. To avoid ambiguity, either import the Prelude hiding these names or qualify uses of these function names with an alias for this module.

Synopsis

The Traversable class

class (Functor t, Foldable t) => Traversable t whereSource

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

Minimal complete definition: traverse or sequenceA.

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.

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:

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.

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

Evaluate each action in the structure from left to right, and collect the results.

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.

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.

Utility functions

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

for is traverse with its arguments flipped.

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

forM is mapM with its arguments flipped.

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 :: Traversable t => (a -> b) -> t a -> t bSource

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

foldMapDefault :: (Traversable t, Monoid m) => (a -> m) -> t a -> mSource

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