Safe Haskell | Safe |
---|---|

Language | Haskell2010 |

- class (Functor t, Foldable t) => Traversable (t :: * -> *) where
- for :: (Traversable t, Applicative f) => t a -> (a -> f b) -> f (t b)
- mapAccumL :: Traversable t => (a -> b -> (a, c)) -> a -> t b -> (a, t c)
- 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.

A definition of `traverse`

must satisfy the following laws:

*naturality*`t .`

for every applicative transformation`traverse`

f =`traverse`

(t . f)`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 .`

for every applicative transformation`sequenceA`

=`sequenceA`

.`fmap`

t`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 Identity 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`

).

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. For a version that ignores
the results see `traverse_`

.

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

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

.

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

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

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

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 :: (Traversable t, Monoid m) => (a -> m) -> t a -> m #