base-4.10.1.0: Basic libraries

CopyrightConor McBride and Ross Paterson 2005
LicenseBSD-style (see the LICENSE file in the distribution)
Maintainer[email protected]
Stabilityexperimental
Portabilityportable
Safe HaskellTrustworthy
LanguageHaskell2010

Data.Traversable

Contents

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.

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:

Minimal complete definition

traverse | sequenceA

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

Traversable [] #

Since: 2.1

Methods

traverse :: 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 #

Traversable Maybe #

Since: 2.1

Methods

traverse :: 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 #

Traversable Par1 # 

Methods

traverse :: 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 #

Traversable Last #

Since: 4.8.0.0

Methods

traverse :: 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 #

Traversable First #

Since: 4.8.0.0

Methods

traverse :: 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 #

Traversable Product #

Since: 4.8.0.0

Methods

traverse :: 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 #

Traversable Sum #

Since: 4.8.0.0

Methods

traverse :: 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 #

Traversable Dual #

Since: 4.8.0.0

Methods

traverse :: 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 #

Traversable Identity # 

Methods

traverse :: 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 #

Traversable ZipList #

Since: 4.9.0.0

Methods

traverse :: 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 #

Traversable NonEmpty #

Since: 4.9.0.0

Methods

traverse :: 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 #

Traversable Option #

Since: 4.9.0.0

Methods

traverse :: 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 #

Traversable Last #

Since: 4.9.0.0

Methods

traverse :: 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 #

Traversable First #

Since: 4.9.0.0

Methods

traverse :: 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 #

Traversable Max #

Since: 4.9.0.0

Methods

traverse :: 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 #

Traversable Min #

Since: 4.9.0.0

Methods

traverse :: 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 #

Traversable Complex # 

Methods

traverse :: 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 #

Traversable (Either a) #

Since: 4.7.0.0

Methods

traverse :: Applicative f => (a -> f b) -> Either a a -> f (Either a b) Source #

sequenceA :: Applicative f => Either a (f a) -> f (Either a a) Source #

mapM :: Monad m => (a -> m b) -> Either a a -> m (Either a b) Source #

sequence :: Monad m => Either a (m a) -> m (Either a a) Source #

Traversable (V1 *) # 

Methods

traverse :: 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 *) #

Since: 4.9.0.0

Methods

traverse :: 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 ((,) a) #

Since: 4.7.0.0

Methods

traverse :: Applicative f => (a -> f b) -> (a, a) -> f (a, b) Source #

sequenceA :: Applicative f => (a, f a) -> f (a, a) Source #

mapM :: Monad m => (a -> m b) -> (a, a) -> m (a, b) Source #

sequence :: Monad m => (a, m a) -> m (a, a) Source #

Traversable (Proxy *) #

Since: 4.7.0.0

Methods

traverse :: 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 #

Traversable (Arg a) #

Since: 4.9.0.0

Methods

traverse :: Applicative f => (a -> f b) -> Arg a a -> f (Arg a b) Source #

sequenceA :: Applicative f => Arg a (f a) -> f (Arg a a) Source #

mapM :: Monad m => (a -> m b) -> Arg a a -> m (Arg a b) Source #

sequence :: Monad m => Arg a (m a) -> m (Arg a a) Source #

Traversable f => Traversable (Rec1 * f) # 

Methods

traverse :: Applicative f => (a -> f b) -> Rec1 * f a -> f (Rec1 * f b) Source #

sequenceA :: Applicative f => Rec1 * f (f a) -> f (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 (URec * Char) # 

Methods

traverse :: Applicative f => (a -> f b) -> URec * Char a -> f (URec * Char b) Source #

sequenceA :: Applicative f => URec * Char (f a) -> f (URec * Char a) Source #

mapM :: Monad m => (a -> m b) -> URec * Char a -> m (URec * Char b) Source #

sequence :: Monad m => URec * Char (m a) -> m (URec * Char a) Source #

Traversable (URec * Double) # 

Methods

traverse :: Applicative f => (a -> f b) -> URec * Double a -> f (URec * Double b) Source #

sequenceA :: Applicative f => URec * Double (f a) -> f (URec * Double a) Source #

mapM :: Monad m => (a -> m b) -> URec * Double a -> m (URec * Double b) Source #

sequence :: Monad m => URec * Double (m a) -> m (URec * Double a) Source #

Traversable (URec * Float) # 

Methods

traverse :: Applicative f => (a -> f b) -> URec * Float a -> f (URec * Float b) Source #

sequenceA :: Applicative f => URec * Float (f a) -> f (URec * Float a) Source #

mapM :: Monad m => (a -> m b) -> URec * Float a -> m (URec * Float b) Source #

sequence :: Monad m => URec * Float (m a) -> m (URec * Float a) Source #

Traversable (URec * Int) # 

Methods

traverse :: Applicative f => (a -> f b) -> URec * Int a -> f (URec * Int b) Source #

sequenceA :: Applicative f => URec * Int (f a) -> f (URec * Int a) Source #

mapM :: Monad m => (a -> m b) -> URec * Int a -> m (URec * Int b) Source #

sequence :: Monad m => URec * Int (m a) -> m (URec * Int a) Source #

Traversable (URec * Word) # 

Methods

traverse :: Applicative f => (a -> f b) -> URec * Word a -> f (URec * Word b) Source #

sequenceA :: Applicative f => URec * Word (f a) -> f (URec * Word a) Source #

mapM :: Monad m => (a -> m b) -> URec * Word a -> m (URec * Word b) Source #

sequence :: Monad m => URec * Word (m a) -> m (URec * Word a) Source #

Traversable (URec * (Ptr ())) # 

Methods

traverse :: Applicative f => (a -> f b) -> URec * (Ptr ()) a -> f (URec * (Ptr ()) b) Source #

sequenceA :: Applicative f => URec * (Ptr ()) (f a) -> f (URec * (Ptr ()) a) Source #

mapM :: Monad m => (a -> m b) -> URec * (Ptr ()) a -> m (URec * (Ptr ()) b) Source #

sequence :: Monad m => URec * (Ptr ()) (m a) -> m (URec * (Ptr ()) a) Source #

Traversable (Const * m) #

Since: 4.7.0.0

Methods

traverse :: 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 m => (a -> m b) -> Const * m a -> m (Const * m b) Source #

sequence :: Monad m => Const * m (m a) -> m (Const * m a) Source #

Traversable (K1 * i c) # 

Methods

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

Methods

traverse :: Applicative f => (a -> f b) -> (* :+: f) g a -> f ((* :+: f) g b) Source #

sequenceA :: Applicative f => (* :+: f) g (f a) -> f ((* :+: 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) # 

Methods

traverse :: Applicative f => (a -> f b) -> (* :*: f) g a -> f ((* :*: f) g b) Source #

sequenceA :: Applicative f => (* :*: f) g (f a) -> f ((* :*: 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) #

Since: 4.9.0.0

Methods

traverse :: Applicative f => (a -> f b) -> Sum * f g a -> f (Sum * f g b) Source #

sequenceA :: Applicative f => Sum * f g (f a) -> f (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) #

Since: 4.9.0.0

Methods

traverse :: Applicative f => (a -> f b) -> Product * f g a -> f (Product * f g b) Source #

sequenceA :: Applicative f => Product * f g (f a) -> f (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) # 

Methods

traverse :: Applicative f => (a -> f b) -> M1 * i c f a -> f (M1 * i c f b) Source #

sequenceA :: Applicative f => M1 * i c f (f a) -> f (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) # 

Methods

traverse :: Applicative f => (a -> f b) -> (* :.: *) f g a -> f ((* :.: *) f g b) Source #

sequenceA :: Applicative f => (* :.: *) f g (f a) -> f ((* :.: *) 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) #

Since: 4.9.0.0

Methods

traverse :: Applicative f => (a -> f b) -> Compose * * f g a -> f (Compose * * f g b) Source #

sequenceA :: Applicative f => Compose * * f g (f a) -> f (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)