Data.Traversable

base-3.0.0.0: Basic libraries

Data.Traversable

Portability	portable
Stability	experimental
Maintainer	ross@soi.city.ac.uk

Description

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

See also

Applicative Programming with Effects, by Conor McBride and Ross Paterson, online at http://www.soi.city.ac.uk/~ross/papers/Applicative.html.
The Essence of the Iterator Pattern, by Jeremy Gibbons and Bruno Oliveira, in Mathematically-Structured Functional Programming, 2006, and online at http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/publications/#iterator.

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

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)

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

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

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

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

fmapDefault :: Traversable t => (a -> b) -> t a -> t b

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

Documentation

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

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

Minimal complete definition: traverse or sequenceA.

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

Methods

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

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)

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)

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)

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

Instances

Traversable Maybe

Traversable []

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

for is traverse with its arguments flipped.

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

forM is mapM with its arguments flipped.

fmapDefault :: Traversable t => (a -> b) -> t a -> t b

This function may be used as a value for fmap in a Functor instance.

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

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

Produced by Haddock version 0.8