base-4.8.1.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 (x `<*>` y) = t x `<*>` t y`

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:

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

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

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

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

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