| Haskell Hierarchical Libraries (base package) | Source code | Contents | Index

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 an 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 Digit
Traversable Elem
Traversable FingerTree
Traversable Maybe
Traversable Node
Traversable Seq
Traversable Tree
Traversable ViewL
Traversable ViewR
Traversable []
Ix i => Traversable (Array i)
Traversable (Map k)

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