base-4.14.0.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.

See also

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 (f <*> x) = t f <*> t x


and the identity functor Identity and composition functors Compose are from Data.Functor.Identity and Data.Functor.Compose.

A result of the naturality law is a purity law for traverse

traverse pure = pure

(The naturality law is implied by parametricity and thus so is the purity law [1, p15].)

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

References:  The Essence of the Iterator Pattern, Jeremy Gibbons and Bruno C. d. S. Oliveira

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

Instances details
 Source # Since: 2.1 Instance detailsDefined in Data.Traversable Methodstraverse :: Applicative f => (a -> f b) -> [a] -> f [b] Source #sequenceA :: Applicative f => [f a] -> f [a] Source #mapM :: Monad m => (a -> m b) -> [a] -> m [b] Source #sequence :: Monad m => [m a] -> m [a] Source # Source # Since: 2.1 Instance detailsDefined in Data.Traversable Methodstraverse :: Applicative f => (a -> f b) -> Maybe a -> f (Maybe b) Source #sequenceA :: Applicative f => Maybe (f a) -> f (Maybe a) Source #mapM :: Monad m => (a -> m b) -> Maybe a -> m (Maybe b) Source #sequence :: Monad m => Maybe (m a) -> m (Maybe a) Source # Source # Since: 4.9.0.0 Instance detailsDefined in Data.Traversable Methodstraverse :: Applicative f => (a -> f b) -> Par1 a -> f (Par1 b) Source #sequenceA :: Applicative f => Par1 (f a) -> f (Par1 a) Source #mapM :: Monad m => (a -> m b) -> Par1 a -> m (Par1 b) Source #sequence :: Monad m => Par1 (m a) -> m (Par1 a) Source # Source # Since: 4.9.0.0 Instance detailsDefined in Data.Traversable Methodstraverse :: Applicative f => (a -> f b) -> NonEmpty a -> f (NonEmpty b) Source #sequenceA :: Applicative f => NonEmpty (f a) -> f (NonEmpty a) Source #mapM :: Monad m => (a -> m b) -> NonEmpty a -> m (NonEmpty b) Source #sequence :: Monad m => NonEmpty (m a) -> m (NonEmpty a) Source # Source # Since: 4.12.0.0 Instance detailsDefined in Data.Traversable Methodstraverse :: Applicative f => (a -> f b) -> Down a -> f (Down b) Source #sequenceA :: Applicative f => Down (f a) -> f (Down a) Source #mapM :: Monad m => (a -> m b) -> Down a -> m (Down b) Source #sequence :: Monad m => Down (m a) -> m (Down a) Source # Source # Since: 4.8.0.0 Instance detailsDefined in Data.Traversable Methodstraverse :: Applicative f => (a -> f b) -> Product a -> f (Product b) Source #sequenceA :: Applicative f => Product (f a) -> f (Product a) Source #mapM :: Monad m => (a -> m b) -> Product a -> m (Product b) Source #sequence :: Monad m => Product (m a) -> m (Product a) Source # Source # Since: 4.8.0.0 Instance detailsDefined in Data.Traversable Methodstraverse :: Applicative f => (a -> f b) -> Sum a -> f (Sum b) Source #sequenceA :: Applicative f => Sum (f a) -> f (Sum a) Source #mapM :: Monad m => (a -> m b) -> Sum a -> m (Sum b) Source #sequence :: Monad m => Sum (m a) -> m (Sum a) Source # Source # Since: 4.8.0.0 Instance detailsDefined in Data.Traversable Methodstraverse :: Applicative f => (a -> f b) -> Dual a -> f (Dual b) Source #sequenceA :: Applicative f => Dual (f a) -> f (Dual a) Source #mapM :: Monad m => (a -> m b) -> Dual a -> m (Dual b) Source #sequence :: Monad m => Dual (m a) -> m (Dual a) Source # Source # Since: 4.8.0.0 Instance detailsDefined in Data.Traversable Methodstraverse :: Applicative f => (a -> f b) -> Last a -> f (Last b) Source #sequenceA :: Applicative f => Last (f a) -> f (Last a) Source #mapM :: Monad m => (a -> m b) -> Last a -> m (Last b) Source #sequence :: Monad m => Last (m a) -> m (Last a) Source # Source # Since: 4.8.0.0 Instance detailsDefined in Data.Traversable Methodstraverse :: Applicative f => (a -> f b) -> First a -> f (First b) Source #sequenceA :: Applicative f => First (f a) -> f (First a) Source #mapM :: Monad m => (a -> m b) -> First a -> m (First b) Source #sequence :: Monad m => First (m a) -> m (First a) Source # Source # Since: 4.9.0.0 Instance detailsDefined in Data.Traversable Methodstraverse :: Applicative f => (a -> f b) -> Identity a -> f (Identity b) Source #sequenceA :: Applicative f => Identity (f a) -> f (Identity a) Source #mapM :: Monad m => (a -> m b) -> Identity a -> m (Identity b) Source #sequence :: Monad m => Identity (m a) -> m (Identity a) Source # Source # Since: 4.9.0.0 Instance detailsDefined in Data.Traversable Methodstraverse :: Applicative f => (a -> f b) -> ZipList a -> f (ZipList b) Source #sequenceA :: Applicative f => ZipList (f a) -> f (ZipList a) Source #mapM :: Monad m => (a -> m b) -> ZipList a -> m (ZipList b) Source #sequence :: Monad m => ZipList (m a) -> m (ZipList a) Source # Source # Since: 4.9.0.0 Instance detailsDefined in Data.Semigroup Methodstraverse :: Applicative f => (a -> f b) -> Option a -> f (Option b) Source #sequenceA :: Applicative f => Option (f a) -> f (Option a) Source #mapM :: Monad m => (a -> m b) -> Option a -> m (Option b) Source #sequence :: Monad m => Option (m a) -> m (Option a) Source # Source # Since: 4.9.0.0 Instance detailsDefined in Data.Semigroup Methodstraverse :: Applicative f => (a -> f b) -> Last a -> f (Last b) Source #sequenceA :: Applicative f => Last (f a) -> f (Last a) Source #mapM :: Monad m => (a -> m b) -> Last a -> m (Last b) Source #sequence :: Monad m => Last (m a) -> m (Last a) Source # Source # Since: 4.9.0.0 Instance detailsDefined in Data.Semigroup Methodstraverse :: Applicative f => (a -> f b) -> First a -> f (First b) Source #sequenceA :: Applicative f => First (f a) -> f (First a) Source #mapM :: Monad m => (a -> m b) -> First a -> m (First b) Source #sequence :: Monad m => First (m a) -> m (First a) Source # Source # Since: 4.9.0.0 Instance detailsDefined in Data.Semigroup Methodstraverse :: Applicative f => (a -> f b) -> Max a -> f (Max b) Source #sequenceA :: Applicative f => Max (f a) -> f (Max a) Source #mapM :: Monad m => (a -> m b) -> Max a -> m (Max b) Source #sequence :: Monad m => Max (m a) -> m (Max a) Source # Source # Since: 4.9.0.0 Instance detailsDefined in Data.Semigroup Methodstraverse :: Applicative f => (a -> f b) -> Min a -> f (Min b) Source #sequenceA :: Applicative f => Min (f a) -> f (Min a) Source #mapM :: Monad m => (a -> m b) -> Min a -> m (Min b) Source #sequence :: Monad m => Min (m a) -> m (Min a) Source # Source # Since: 4.9.0.0 Instance detailsDefined in Data.Complex Methodstraverse :: Applicative f => (a -> f b) -> Complex a -> f (Complex b) Source #sequenceA :: Applicative f => Complex (f a) -> f (Complex a) Source #mapM :: Monad m => (a -> m b) -> Complex a -> m (Complex b) Source #sequence :: Monad m => Complex (m a) -> m (Complex a) Source # Source # Since: 4.7.0.0 Instance detailsDefined in Data.Traversable Methodstraverse :: Applicative f => (a0 -> f b) -> Either a a0 -> f (Either a b) Source #sequenceA :: Applicative f => Either a (f a0) -> f (Either a a0) Source #mapM :: Monad m => (a0 -> m b) -> Either a a0 -> m (Either a b) Source #sequence :: Monad m => Either a (m a0) -> m (Either a a0) Source # Traversable (V1 :: Type -> Type) Source # Since: 4.9.0.0 Instance detailsDefined in Data.Traversable Methodstraverse :: Applicative f => (a -> f b) -> V1 a -> f (V1 b) Source #sequenceA :: Applicative f => V1 (f a) -> f (V1 a) Source #mapM :: Monad m => (a -> m b) -> V1 a -> m (V1 b) Source #sequence :: Monad m => V1 (m a) -> m (V1 a) Source # Traversable (U1 :: Type -> Type) Source # Since: 4.9.0.0 Instance detailsDefined in Data.Traversable Methodstraverse :: Applicative f => (a -> f b) -> U1 a -> f (U1 b) Source #sequenceA :: Applicative f => U1 (f a) -> f (U1 a) Source #mapM :: Monad m => (a -> m b) -> U1 a -> m (U1 b) Source #sequence :: Monad m => U1 (m a) -> m (U1 a) Source # Traversable (UAddr :: Type -> Type) Source # Since: 4.9.0.0 Instance detailsDefined in Data.Traversable Methodstraverse :: Applicative f => (a -> f b) -> UAddr a -> f (UAddr b) Source #sequenceA :: Applicative f => UAddr (f a) -> f (UAddr a) Source #mapM :: Monad m => (a -> m b) -> UAddr a -> m (UAddr b) Source #sequence :: Monad m => UAddr (m a) -> m (UAddr a) Source # Traversable (UChar :: Type -> Type) Source # Since: 4.9.0.0 Instance detailsDefined in Data.Traversable Methodstraverse :: Applicative f => (a -> f b) -> UChar a -> f (UChar b) Source #sequenceA :: Applicative f => UChar (f a) -> f (UChar a) Source #mapM :: Monad m => (a -> m b) -> UChar a -> m (UChar b) Source #sequence :: Monad m => UChar (m a) -> m (UChar a) Source # Source # Since: 4.9.0.0 Instance detailsDefined in Data.Traversable Methodstraverse :: Applicative f => (a -> f b) -> UDouble a -> f (UDouble b) Source #sequenceA :: Applicative f => UDouble (f a) -> f (UDouble a) Source #mapM :: Monad m => (a -> m b) -> UDouble a -> m (UDouble b) Source #sequence :: Monad m => UDouble (m a) -> m (UDouble a) Source # Source # Since: 4.9.0.0 Instance detailsDefined in Data.Traversable Methodstraverse :: Applicative f => (a -> f b) -> UFloat a -> f (UFloat b) Source #sequenceA :: Applicative f => UFloat (f a) -> f (UFloat a) Source #mapM :: Monad m => (a -> m b) -> UFloat a -> m (UFloat b) Source #sequence :: Monad m => UFloat (m a) -> m (UFloat a) Source # Traversable (UInt :: Type -> Type) Source # Since: 4.9.0.0 Instance detailsDefined in Data.Traversable Methodstraverse :: Applicative f => (a -> f b) -> UInt a -> f (UInt b) Source #sequenceA :: Applicative f => UInt (f a) -> f (UInt a) Source #mapM :: Monad m => (a -> m b) -> UInt a -> m (UInt b) Source #sequence :: Monad m => UInt (m a) -> m (UInt a) Source # Traversable (UWord :: Type -> Type) Source # Since: 4.9.0.0 Instance detailsDefined in Data.Traversable Methodstraverse :: Applicative f => (a -> f b) -> UWord a -> f (UWord b) Source #sequenceA :: Applicative f => UWord (f a) -> f (UWord a) Source #mapM :: Monad m => (a -> m b) -> UWord a -> m (UWord b) Source #sequence :: Monad m => UWord (m a) -> m (UWord a) Source # Source # Since: 4.7.0.0 Instance detailsDefined in Data.Traversable Methodstraverse :: Applicative f => (a0 -> f b) -> (a, a0) -> f (a, b) Source #sequenceA :: Applicative f => (a, f a0) -> f (a, a0) Source #mapM :: Monad m => (a0 -> m b) -> (a, a0) -> m (a, b) Source #sequence :: Monad m => (a, m a0) -> m (a, a0) Source # Ix i => Traversable (Array i) Source # Since: 2.1 Instance detailsDefined in Data.Traversable Methodstraverse :: Applicative f => (a -> f b) -> Array i a -> f (Array i b) Source #sequenceA :: Applicative f => Array i (f a) -> f (Array i a) Source #mapM :: Monad m => (a -> m b) -> Array i a -> m (Array i b) Source #sequence :: Monad m => Array i (m a) -> m (Array i a) Source # Traversable (Proxy :: Type -> Type) Source # Since: 4.7.0.0 Instance detailsDefined in Data.Traversable Methodstraverse :: Applicative f => (a -> f b) -> Proxy a -> f (Proxy b) Source #sequenceA :: Applicative f => Proxy (f a) -> f (Proxy a) Source #mapM :: Monad m => (a -> m b) -> Proxy a -> m (Proxy b) Source #sequence :: Monad m => Proxy (m a) -> m (Proxy a) Source # Source # Since: 4.9.0.0 Instance detailsDefined in Data.Semigroup Methodstraverse :: Applicative f => (a0 -> f b) -> Arg a a0 -> f (Arg a b) Source #sequenceA :: Applicative f => Arg a (f a0) -> f (Arg a a0) Source #mapM :: Monad m => (a0 -> m b) -> Arg a a0 -> m (Arg a b) Source #sequence :: Monad m => Arg a (m a0) -> m (Arg a a0) Source # Traversable f => Traversable (Rec1 f) Source # Since: 4.9.0.0 Instance detailsDefined in Data.Traversable Methodstraverse :: Applicative f0 => (a -> f0 b) -> Rec1 f a -> f0 (Rec1 f b) Source #sequenceA :: Applicative f0 => Rec1 f (f0 a) -> f0 (Rec1 f a) Source #mapM :: Monad m => (a -> m b) -> Rec1 f a -> m (Rec1 f b) Source #sequence :: Monad m => Rec1 f (m a) -> m (Rec1 f a) Source # Traversable f => Traversable (Alt f) Source # Since: 4.12.0.0 Instance detailsDefined in Data.Traversable Methodstraverse :: Applicative f0 => (a -> f0 b) -> Alt f a -> f0 (Alt f b) Source #sequenceA :: Applicative f0 => Alt f (f0 a) -> f0 (Alt f a) Source #mapM :: Monad m => (a -> m b) -> Alt f a -> m (Alt f b) Source #sequence :: Monad m => Alt f (m a) -> m (Alt f a) Source # Traversable f => Traversable (Ap f) Source # Since: 4.12.0.0 Instance detailsDefined in Data.Traversable Methodstraverse :: Applicative f0 => (a -> f0 b) -> Ap f a -> f0 (Ap f b) Source #sequenceA :: Applicative f0 => Ap f (f0 a) -> f0 (Ap f a) Source #mapM :: Monad m => (a -> m b) -> Ap f a -> m (Ap f b) Source #sequence :: Monad m => Ap f (m a) -> m (Ap f a) Source # Traversable (Const m :: Type -> Type) Source # Since: 4.7.0.0 Instance detailsDefined in Data.Traversable Methodstraverse :: Applicative f => (a -> f b) -> Const m a -> f (Const m b) Source #sequenceA :: Applicative f => Const m (f a) -> f (Const m a) Source #mapM :: Monad m0 => (a -> m0 b) -> Const m a -> m0 (Const m b) Source #sequence :: Monad m0 => Const m (m0 a) -> m0 (Const m a) Source # Traversable (K1 i c :: Type -> Type) Source # Since: 4.9.0.0 Instance detailsDefined in Data.Traversable Methodstraverse :: Applicative f => (a -> f b) -> K1 i c a -> f (K1 i c b) Source #sequenceA :: Applicative f => K1 i c (f a) -> f (K1 i c a) Source #mapM :: Monad m => (a -> m b) -> K1 i c a -> m (K1 i c b) Source #sequence :: Monad m => K1 i c (m a) -> m (K1 i c a) Source # (Traversable f, Traversable g) => Traversable (f :+: g) Source # Since: 4.9.0.0 Instance detailsDefined in Data.Traversable Methodstraverse :: Applicative f0 => (a -> f0 b) -> (f :+: g) a -> f0 ((f :+: g) b) Source #sequenceA :: Applicative f0 => (f :+: g) (f0 a) -> f0 ((f :+: g) a) Source #mapM :: Monad m => (a -> m b) -> (f :+: g) a -> m ((f :+: g) b) Source #sequence :: Monad m => (f :+: g) (m a) -> m ((f :+: g) a) Source # (Traversable f, Traversable g) => Traversable (f :*: g) Source # Since: 4.9.0.0 Instance detailsDefined in Data.Traversable Methodstraverse :: Applicative f0 => (a -> f0 b) -> (f :*: g) a -> f0 ((f :*: g) b) Source #sequenceA :: Applicative f0 => (f :*: g) (f0 a) -> f0 ((f :*: g) a) Source #mapM :: Monad m => (a -> m b) -> (f :*: g) a -> m ((f :*: g) b) Source #sequence :: Monad m => (f :*: g) (m a) -> m ((f :*: g) a) Source # (Traversable f, Traversable g) => Traversable (Sum f g) Source # Since: 4.9.0.0 Instance detailsDefined in Data.Functor.Sum Methodstraverse :: Applicative f0 => (a -> f0 b) -> Sum f g a -> f0 (Sum f g b) Source #sequenceA :: Applicative f0 => Sum f g (f0 a) -> f0 (Sum f g a) Source #mapM :: Monad m => (a -> m b) -> Sum f g a -> m (Sum f g b) Source #sequence :: Monad m => Sum f g (m a) -> m (Sum f g a) Source # (Traversable f, Traversable g) => Traversable (Product f g) Source # Since: 4.9.0.0 Instance detailsDefined in Data.Functor.Product Methodstraverse :: Applicative f0 => (a -> f0 b) -> Product f g a -> f0 (Product f g b) Source #sequenceA :: Applicative f0 => Product f g (f0 a) -> f0 (Product f g a) Source #mapM :: Monad m => (a -> m b) -> Product f g a -> m (Product f g b) Source #sequence :: Monad m => Product f g (m a) -> m (Product f g a) Source # Traversable f => Traversable (M1 i c f) Source # Since: 4.9.0.0 Instance detailsDefined in Data.Traversable Methodstraverse :: Applicative f0 => (a -> f0 b) -> M1 i c f a -> f0 (M1 i c f b) Source #sequenceA :: Applicative f0 => M1 i c f (f0 a) -> f0 (M1 i c f a) Source #mapM :: Monad m => (a -> m b) -> M1 i c f a -> m (M1 i c f b) Source #sequence :: Monad m => M1 i c f (m a) -> m (M1 i c f a) Source # (Traversable f, Traversable g) => Traversable (f :.: g) Source # Since: 4.9.0.0 Instance detailsDefined in Data.Traversable Methodstraverse :: Applicative f0 => (a -> f0 b) -> (f :.: g) a -> f0 ((f :.: g) b) Source #sequenceA :: Applicative f0 => (f :.: g) (f0 a) -> f0 ((f :.: g) a) Source #mapM :: Monad m => (a -> m b) -> (f :.: g) a -> m ((f :.: g) b) Source #sequence :: Monad m => (f :.: g) (m a) -> m ((f :.: g) a) Source # (Traversable f, Traversable g) => Traversable (Compose f g) Source # Since: 4.9.0.0 Instance detailsDefined in Data.Functor.Compose Methodstraverse :: Applicative f0 => (a -> f0 b) -> Compose f g a -> f0 (Compose f g b) Source #sequenceA :: Applicative f0 => Compose f g (f0 a) -> f0 (Compose f g a) Source #mapM :: Monad m => (a -> m b) -> Compose f g a -> m (Compose f g b) Source #sequence :: Monad m => Compose f g (m a) -> m (Compose f g a) Source #

# 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 :: forall t a b. 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.)

fmapDefault f ≡ runIdentity . traverse (Identity . f)


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

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

foldMapDefault f ≡ getConst . traverse (Const . f)